2092. 找出知曉秘密的所有專家

小貼士：建議先了解並查集

思路

可能會有多個會議，比如時間單位 10 有兩個會議，第一個會議有 $[1,2,3]$ 三人，第二個會議有 $[4,5]$ 兩人，
我們要讓知曉秘密的人將秘密散布出去，假設 $2$ 知曉秘密，在這個時間單位後，$[1,2]$兩人也會知道秘密。

所以要完成三個功能：

1. 紀錄知曉秘密的人。
2. 紀錄每個時間單位開的會有那些人，有幾個會議在開。
3. 讓知曉秘密的人傳遞秘密。

先將時間排序，方便後續將同一時間開的會統一計算。
為了讓祕密只被傳遞到相同會議中的人，建立一個表，紀錄每個人在這個時間「跟誰在開會」。
在把「相同時間中所有會議紀錄」都統計到表中後，
透過深度優先搜索，讓知曉秘密的人把秘密傳遞出去。

程式碼

1. dfs

class Solution {
public:
    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
        unordered_set<int> uset = {0, firstPerson}; // 紀錄知曉秘密的人
        ranges::sort(meetings, {}, [](auto& a) { return a[2]; }); // 根據時間排序
        int m = meetings.size();
        int x, y, time;
        for(int i = 0; i < m;) {
            time = meetings[i][2];
            unordered_map<int, vector<int>> graph;
            for(; i < m && meetings[i][2] == time; ++i) {// 將同時間發生的會議建表
                x = meetings[i][0], y = meetings[i][1];
                graph[x].push_back(y);
                graph[y].push_back(x);
            }
            unordered_map<int, bool> visited;
            auto dfs = [&](this auto&& dfs, int x) -> void { // 從 x 往外擴, x 知曉秘密
                for(auto& neighbor : graph[x]) {
                    if(visited.contains(neighbor)) { // 如果走訪過, 略過
                        continue;
                    }
                    visited[neighbor] = true;
                    uset.insert(neighbor); // 鄰居知曉秘密
                    dfs(neighbor);
                }
            };
            for(auto& [x, _] : graph) {
                if(uset.contains(x) && !visited.contains(x)) { // 知曉秘密, 且未走訪
                    dfs(x);
                }
            }
        }
        return vector(uset.begin(), uset.end());
    }
};

複雜度分析

• 時間複雜度：方法一 $O(m\log{m})$，
• 空間複雜度：方法一 $O(m)$，

第二個方法是使用並查集。 用並查集取代方法一的「鄰接表」，順帶紀錄「知曉秘密的人」。 由於最初只有0跟firstPerson知曉秘密， 而0在會議記錄當中永遠不會出現，能利用這個特性， 判斷建立好的表中，專家x是否跟0相鄰。

• 如果相鄰，專家x的根結點跟0會相同。
• 如果不相鄰，專家x的根結點跟0不同。 假如發現根結點不同，就將合併的操作撤銷（將根節點重新設為自己）。

2. 並查集

class UnionFind {
public:
    vector<int> parent;
    UnionFind(int n) : parent(n) {
        ranges::iota(parent, 0);
    }
    int find_parent(int x) {
        if(parent[x] != x) {
            parent[x] = find_parent(parent[x]); 
        }
        return parent[x];
    }
    bool is_same(int x, int y) {
        return find_parent(x) == find_parent(y);
    }
    void merge(int x, int y) {
        x = find_parent(x), y = find_parent(y);
        parent[x] = y;
    }
};
class Solution {
public:
    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
        ranges::sort(meetings, {}, [](auto& a) { return a[2]; }); // 根據時間排序
        
        UnionFind unionfind(n);
        unionfind.merge(0, firstPerson);
        
        int m = meetings.size();
        int x, y, time;
        for(int i = 0; i < m;) {
            int start = i;
            time = meetings[i][2]; // 將同一個時間的開會專家合併
            for(; i < m && meetings[i][2] == time; ++i) {
                unionfind.merge(meetings[i][0], meetings[i][1]);
            }
            for(int j = start; j < i; ++j) { 
                // 假如合併之後，跟 0 不在同一個集合（這一群沒有知曉秘密的人）撤銷合併
                x = meetings[j][0], y = meetings[j][1];
                if(!unionfind.is_same(x, 0)) {
                    unionfind.parent[x] = x;
                }
                if(!unionfind.is_same(y, 0)) {
                    unionfind.parent[y] = y;
                }
            }
        }
        vector<int> res;
        for(int i = 0; i < n; ++i) {
            if(unionfind.is_same(i, 0)) {
                res.push_back(i);
            }
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n + m\log{m})$
• 空間複雜度：$O(n)$