1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

public static int MAXN = 100001;
	public static int[] father = new int[MAXN];
	public static boolean[] secret = new boolean[MAXN];

	public static void build(int n,int first){
		for(int i=0;i<n;i++){
			father[i]=i;
			secret[i]=false;
		}
		father[first]=0;
		secret[0]=true;
	}

	public static int find(int i){
		if(i!=father[i]){
			father[i]=find(father[i]);
		}
		return father[i];
	}

	public static void union(int x,int y){
		int fx = find(x);
		int fy = find(y);

		if(fx!=fy){
			father[fx]=fy;
			secret[fy]|=secret[fx];
		}
	}

	public static List<Integer> findAllPeople(int n,int[][] meetings,int first){
		build(n, first);

		Arrays.sort(meetings,(a,b)->a[2]-b[2]);
		int m = meetings.length;
		for(int l=0,r;l<m;){
			r=l;
			while (r+1<m&&meetings[l][2]==meetings[r+1][2]) {
				r++;
			}

			for(int i=l;i<=r;i++){
				union(meetings[i][0], meetings[i][1]);
			}

			for(int i=l,a,b;i<=r;i++){
				a=meetings[i][0];
				b=meetings[i][1];
				if(!secret[find(a)]){
					father[a]=a;
				}
				if(!secret[find(b)]){
					father[b]=b;
				}
			}
			l=r+1;
		}

		List<Integer> ans = new ArrayList<>();
		for(int i=0;i<n;i++){
			if(secret[find(i)]){
				ans.add(i);
			}
		}
		return ans;
	}