LeetCode 2092. 找出知晓秘密的所有专家（并查集）

示例 1：
输入：n = 6, meetings = [[1,2,5],[2,3,8],[1,5,10]], firstPerson = 1
输出：[0,1,2,3,5]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 5 ，专家 1 将秘密与专家 2 共享。
时间 8 ，专家 2 将秘密与专家 3 共享。
时间 10 ，专家 1 将秘密与专家 5 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 5 都将知晓这个秘密。
示例 2：
输入：n = 4, meetings = [[3,1,3],[1,2,2],[0,3,3]], firstPerson = 3
输出：[0,1,3]
解释：
时间 0 ，专家 0 将秘密与专家 3 共享。
时间 2 ，专家 1 与专家 2 都不知晓这个秘密。
时间 3 ，专家 3 将秘密与专家 0 和专家 1 共享。
因此，在所有会议结束后，专家 0、1 和 3 都将知晓这个秘密。
示例 3：
输入：n = 5, meetings = [[3,4,2],[1,2,1],[2,3,1]], firstPerson = 1
输出：[0,1,2,3,4]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 1 ，专家 1 将秘密与专家 2 共享，专家 2 将秘密与专家 3 共享。
注意，专家 2 可以在收到秘密的同一时间分享此秘密。
时间 2 ，专家 3 将秘密与专家 4 共享。
因此，在所有会议结束后，专家 0、1、2、3 和 4 都将知晓这个秘密。
示例 4：
输入：n = 6, meetings = [[0,2,1],[1,3,1],[4,5,1]], firstPerson = 1
输出：[0,1,2,3]
解释：
时间 0 ，专家 0 将秘密与专家 1 共享。
时间 1 ，专家 0 将秘密与专家 2 共享，专家 1 将秘密与专家 3 共享。
因此，在所有会议结束后，专家 0、1、2 和 3 都将知晓这个秘密。
提示：
2 <= n <= 10^5
1 <= meetings.length <= 10^5
meetings[i].length == 3
0 <= xi, yi <= n - 1
xi != yi
1 <= timei <= 10^5
1 <= firstPerson <= n - 1

class dsu{
public:
    vector<int> f;
    dsu(int n)
    {
        f.resize(n);
        for(int i = 0; i < n; ++i)
            f[i] = i;
    }
    void merge(int a, int b)
    {
        int fa = find(a), fb = find(b);
        f[fa] = fb;
    }
    int find(int a)
    {
        if(a == f[a]) return a;
        return f[a] = find(f[a]);
    }
    void unmerge(int a)
    {
        f[a] = a;
    }
};
class Solution {
public:
    vector<int> findAllPeople(int n, vector<vector<int>>& meetings, int firstPerson) {
        int mlen = meetings.size();
        vector<bool> known(n, false);
        known[0] = known[firstPerson] = true;
        sort(meetings.begin(), meetings.end(),[&](auto& a, auto& b){
            return a[2] < b[2];
        });
        dsu uset(n);
        for(int i = 0; i < mlen; )
        {
            int t = meetings[i][2], j = i;
            while(j < mlen && meetings[j][2]==t)
            {   // 时间相同的会议
                int a = meetings[j][0], b = meetings[j][1];
                int f1 = uset.find(a);
                int f2 = uset.find(b);
                if(known[f2]) // b 知道秘密
                    uset.merge(a, b);//有顺序的，注意！！！
                else
                    uset.merge(b, a);
                j++;
            }
            for(int k = i; k < j; ++k)
            {
                int a = meetings[k][0], b = meetings[k][1];
                int f1 = uset.find(a);
                int f2 = uset.find(b);
                if(known[f1] || known[f2])
                    known[a]=known[b]=true;
                else
                { // 两人都不知道秘密，恢复他们的初始状态
                    uset.unmerge(a);
                    uset.unmerge(b);
                }
            }
            i = j;
        }
        vector<int> ans;
        for(int i = 0; i < n; ++i)
            if(known[i])
                ans.push_back(i);
        return ans;
    }
};