---
# System prepended metadata

title: 2092. Find All People With Secret

---

Daily 24/02/2024: [2092. Find All People With Secret](https://leetcode.com/problems/find-all-people-with-secret/)

# 1. Tóm tắt đề bài
Cho một số nguyên ```n``` cho biết có ```n``` người được đánh số từ ```0``` đến ```n - 1```. Bạn cũng được cung cấp một mảng số nguyên ```meetings```, ```meetings[i] = [xi, yi, timei]``` trong đó cho biết người ```xi``` và người ```yi``` có cuộc họp lúc ```timei```. Một người có thể tham dự nhiều cuộc họp cùng một lúc. Cuối cùng, bạn được cho một số nguyên ```firstPerson```.

Người số ```0``` có một **bí mật** với ```firstPerson``` và ban đầu sẽ chia sẻ bí mật đó tại thời điểm 0. Bí mật này sau đó sẽ được chia sẻ mỗi khi cuộc gặp diễn ra với người nắm giữ bí mật. Chính thức hơn, trong mỗi cuộc gặp, nếu một người ```xi``` có bí mật tại ```timei```, thì họ sẽ chia sẻ bí mật đó với người ```yi``` và ngược lại.

Những bí mật được chia sẻ ngay lập tức. Nghĩa là, một người có thể nhận được bí mật và chia sẻ nó với mọi người trong các cuộc họp khác trong cùng khung thời gian.

Trả về danh sách tất cả những người có bí mật sau khi tất cả các cuộc họp đã diễn ra. Bạn có thể trả lời câu trả lời theo thứ tự bất kỳ.


#### Giới hạn
- $2 \le$ ```n``` $\le 10^5$
- $1 \le$ ```meetings.length``` $\le 10^5$
- $1 \le$ $x_i, y_i$, ```firstPerson``` $\le n - 1$
- $x_i \ne y_i$
- $1 \le$ $time_i$ $\le 10^5$

# 2. Tóm tắt lời giải

#### Phân tích
- Bài tập thực ra không khó, chúng ta chỉ cần thực hiện lần lượt BFS theo từng thời điểm.
- Đầu tiên chúng ta phải sắp xếp các cuộc họp theo thời điểm diễn ra. Và tại mỗi thời điểm thì xây dựng một graph riêng, từ những người biết bí mật (chúng ta sẽ cho vào một mảng) thì sử dụng BFS để **tuồn bí mật** ra. Sau đó đơn giản là thêm những người mới vào mảng này.
- Thực hiện lần lượt hết các cuộc họp thì hoàn thành bài toán.
# 3. Lời giải chi tiết

#### Code

```python 
class Solution:
    def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]:
        known_set = set([0, firstPerson])
        
        sorted_meetings = []
        meetings.sort(key=lambda x:x[2])

        seen_time = set()
        
        for meeting in meetings:
            if meeting[2] not in seen_time:
                seen_time.add(meeting[2])
                sorted_meetings.append([])
            sorted_meetings[-1].append((meeting[0], meeting[1]))

        for meeting_group in sorted_meetings:
            people_know_secret = set()
            graph = defaultdict(list)
            
            for p1, p2 in meeting_group:
                graph[p1].append(p2)
                graph[p2].append(p1)
                if p1 in known_set:
                    people_know_secret.add(p1)
                if p2 in known_set:
                    people_know_secret.add(p2)
                    
            queue = deque((people_know_secret))
        
            while queue:
                curr = queue.popleft()
                known_set.add(curr)
                for neighbor in graph[curr]:
                    if neighbor not in known_set:
                        known_set.add(neighbor)
                        queue.append(neighbor)

        return list(known_set)

            
```
#### Độ phức tạp
$O(nlog(n) + m)$ trong đó ```n``` là số lượng cuộc họp và ```m``` là  tổng số người tham dự trong tất cả các cuộc họp.
# 4. Kết luận & gợi ý mở rộng
- Năm mới vui vẻ chill chill.

> Hãy dùng nghị lực và sự kiên trì để đánh bại mọi thứ.

###### #Hashtag: <span style='color: blue'>Hash Map</span>