洛谷 P3367 【模板】并查集

 1 #include<cstdio>
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 int f[100005];
 7 int x, y, z;
 8 
 9 inline int find(int x){
10     if(f[x] != x)
11         f[x] = find(f[x]);
12     return f[x];
13 }//递归求父节点，即"查" 
14 
15 int main(){
16     int n, m;
17     scanf("%d%d", &n, &m);
18     for(int i = 1; i <= n; i++) f[i] = i;
19     for(int i = 1; i <= m; i++){
20         scanf("%d%d%d", &z, &x, &y);
21         if(z == 1){
22             int r1 = find(x);
23             int r2 = find(y);
24             f[r1] = r2;
25         }
26         else if(z == 2){
27             int r1 = find(x);
28             int r2 = find(y);
29             if(r1 == r2) printf("Y\n");
30             else printf("N\n");
31         }
32     }
33     return 0;
34 }