原题链接

并查集模板题

当两个点互相可达,我们称它们连通.本题判断连通点的个数,就是判断同一集合下点的个数,一棵树下子节点各不同,因此用数组sizes记录下标为根节点的点的个数

 1 #include <iostream>
 2 using namespace std;
 3 const int N = 1e5+10;
 4 int p[N],sizes[N];
 5 int find(int x)
 6 {
 7     if(p[x]!=x) p[x] = find(p[x]);
 8     return p[x];
 9 }
10 int main()
11 {
12     int n,m;
13     char op[3];
14     scanf("%d%d",&n,&m);
15     for(int i=1;i<=n;i++) { p[i] = i;sizes[i] =1; }
16     while(m--){
17         scanf("%s",op);
18         if(op[0]=='C') {
19             int x,y;
20             scanf("%d%d",&x,&y);
21             if(find(x)==find(y)) continue;
22             sizes[find(y)]+=sizes[find(x)];
23             p[find(x)] = find(y);
24         }
25         else if(op[0]=='Q'){
26             if(op[1]=='1'){
27                 int x,y;
28                 scanf("%d%d",&x,&y);
29                 if(find(p[x])==find(p[y])) printf("Yes\n");
30                 else printf("No\n");
31             }else if(op[1]=='2'){
32                 int x; scanf("%d",&x);
33                 printf("%d\n",sizes[find(x)]);
34             }
35         }
36     }
37     return 0;
38 }