【题解】找出知晓秘密的所有专家

发布时间 : 2026-04-01 10:07

找出知晓秘密的所有专家
给你一个整数 n ，表示有 n 个专家从 0 到 n - 1 编号。另外给你一个下标从 0 开始的二维整数数组 meetings ，其中 meetings[i] = [xi, yi, timei] 表示专家 xi 和专家 yi 在时间 timei 要开一场会。一个专家可以同时参加 多场会议 。最后，给你一个整数 firstPerson 。

专家 0 有一个秘密，最初，他在时间 0 将这个秘密分享给了专家 firstPerson 。接着，这个秘密会在每次有知晓这个秘密的专家参加会议时进行传播。更正式的表达是，每次会议，如果专家 xi 在时间 timei 时知晓这个秘密，那么他将会与专家 yi 分享这个秘密，反之亦然。

秘密共享是 瞬时发生 的。也就是说，在同一时间，一个专家不光可以接收到秘密，还能在其他会议上与其他专家分享。

在所有会议都结束之后，返回所有知晓这个秘密的专家列表。你可以按 任何顺序 返回答案。

显然在同一时刻，相接触的专家合并到一个集合，增加一个数组sec来标记是否知道秘密。
根据时间排序后，按照时间一批一批地处理,如果这个时刻结束专家还不知道秘密就把他们拆散。
最后遍历专家看看它们的集合是否被标记

class Solution {
public:
    int fa[100001];
    bool sec[100001];

    int find(int x) {
        if (fa[x] != x) {
            fa[x] = find(fa[x]);  // 路径压缩
        }
        return fa[x];
    }

    void merge(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx != fy) {
            fa[fx] = fy;  // 合并两个集合
            sec[fy] |= sec[fx];  // 更新秘密信息
        }
    }

    void reset(int x) {
        fa[x] = x;
        sec[x] = 0;
    }

    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
        // 初始化并查集
        for (int i = 0; i < n; i++) {
            fa[i] = i;
            sec[i] = 0;
        }
        sec[firstPerson] = sec[0] = 1;

        // 按时间排序会议
        sort(meetings.begin(), meetings.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[2] < b[2];
        });

        int m = meetings.size();
        for (int l = 0, r; l < m;) {
            r = l;
            // 找到相同时间的会议
            while (r + 1 < m && meetings[r + 1][2] == meetings[l][2]) {
                r++;
            }

            // 临时保存需要重置的节点
            vector<int> toReset;

            // 合并相同时间的会议中的节点
            for (int i = l; i <= r; i++) {
                int x = meetings[i][0], y = meetings[i][1];
                merge(x, y);
                toReset.push_back(x);
                toReset.push_back(y);
            }

            // 重置不包含秘密的节点
            for (int x : toReset) {
                if (!sec[find(x)]) {
                    reset(x);
                }
            }

            l = r + 1;
        }

        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (sec[find(i)]) {
                ans.push_back(i);
            }
        }

        return ans;
    }
};

【题解】 找出知晓秘密的所有专家

【题解】找出知晓秘密的所有专家