# 2092. Find All People With Secret
###### tags: `Leetcode` `Hard` `Union Find`
Link: https://leetcode.com/problems/find-all-people-with-secret/description/
## 思路
直觉的思路是先按照时间排序 然后把知道secret的人都放进去 来了一个新的meeting 就看这两个人有没有一个已经在set里面
但是需要注意的是 对于一批同时间的会议，可能第一个会议的A和B都不知道，但是在第二个会议里B从C知道了这个秘密，那么根据规则A也会在此时刻知道这个秘密。加入第三个会议是A与D，那么D也应该知道秘密
所以我们在这里用一个小union find把同一时间开会的所有人放进去 如果有一个人知道就所有人都知道 但是如果有一个人不知道 我们需要撤回combine()的操作 也就是把这个人的fa设成它自己
## Code

class Solution {
    int[] fa;
    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        Arrays.sort(meetings, (a,b)->(a[2]-b[2]));
        Set<Integer> know = new HashSet<>();
        fa = new int[n];
        for(int i=0; i<n; i++) fa[i] = i;
        fa[firstPerson] = 0;
        know.add(0);
        know.add(firstPerson);
        for(int i=0; i<meetings.length; i++){
            Set<Integer> temp = new HashSet<>();
            int j = i;
            for(j=i; j<meetings.length && meetings[i][2]==meetings[j][2]; j++){
                int a = meetings[j][0], b = meetings[j][1];
                temp.add(a);
                temp.add(b);
                combine(a, b);
            }
            for(int ppl:temp){
                if(find(ppl)!=0) fa[ppl]=ppl;
                else know.add(ppl);
            }
            i = j-1;
        }
        List<Integer> ans = new ArrayList<>(know);
        return ans;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        return fa[a] = find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        if(a<b) fa[b] = a;
        else fa[a] = b;
    }
}