洛谷 P3367 【模板】并查集

嗯...

题目链接：https://www.luogu.org/problemnew/show/P3367

并查集可以支持的操作：“并”和“查”。然后这道题主要就是考察这两种操作。将每一个点的“父亲”初始化为自己，然后分别进行“并”和“查”。

“并”：用递归函数find来查找每一个点的父节点。然后将其中一个父节点设为另一个父节点的父亲即可。

“查”：用递归函数find来查找每一个点的父节点。判断父节点是否相同即可。

AC代码：

 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
");
30             else printf("N
");
31         }
32     }
33     return 0;
34 }

AC代码