给定一个包含 nn 个点（编号为 1∼n1∼n）的无向图，初始时图中没有边。
现在要进行 mm 个操作，操作共有三种：
C a b，在点 aa 和点 bb 之间连一条边，aa 和 bb 可能相等；
Q1 a b，询问点 aa 和点 bb 是否在同一个连通块中，aa 和 bb 可能相等；
Q2 a，询问点 aa 所在连通块中点的数量；
输入格式
第一行输入整数 nn 和 mm。
接下来 mm 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b，如果 aa 和 bb 在同一个连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 aa 所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤1051≤n,m≤105
输入样例：
5 5 C 1 2 Q1 1 2 Q2 1 C 2 5 Q2 5
输出样例：
Yes 2 3
#include <bits/stdc++.h> using namespace std; const int N = 100010; int n,m; int p[N],siz[N]; int find (int x) { if(p[x] != x ) p[x] = find(p[x]); //父节点等于祖宗节点 return p[x]; } int main() { cin>>n>>m; for(int i = 1;i <= n; i ++) { p[i] = i;; siz[i] = 1; } while(m--) { char op[2]; int a,b; scanf("%s",op); if(op[0] == 'C') { scanf("%d%d",&a,&b); if(find(a) == find(b)) continue; siz[find(b)] += siz[find(a)]; p[find(a)] = find(b); //使a的祖宗节点的父节点等于b的父节点实现转接 } else if(op[1] == '1') { scanf("%d%d",&a,&b); if(find(a) == find(b)) puts("Yes"); else puts("No"); } else { scanf("%d",&a); printf("%d\n",siz[find(a)]); } } return 0; }
