AcWing-AcWing 837. 连通块中点的数量

在原来并查集的基础上增加一个Size数组，Size的初始化是必须先每个元素初始化为1
Size只对根节点有效，比如Size[find(1)]就是找1的祖先节点，然后访问祖先节点的个数。当我们联通a点和b点时，如果已经是联通状态了，那么无需继续执行，跳过。否则，那么我们可以把a点加入到b点，然后只对b点所在祖先节点的数量加上a祖先节点的数量，也就是Size[find(b)]+=Size[find(a)];

#include<iostream> #define LEN 100086 #include<string> using namespace std; int n,m,p[LEN],Size[LEN]; string op; 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;          Size[i]=1;     }     while(m--){         cin>>op;         int a,b;         if(op=="C"){             cin>>a>>b;             if(find(a)==find(b))                 continue;             Size[find(b)]+=Size[find(a)];             p[find(a)]=find(b);         }else if(op=="Q1"){             cin>>a>>b;             bool isIn=(find(a)==find(b));             cout<<(isIn?"Yes":"No")<<endl;         }else if(op=="Q2"){             cin>>a;             cout<<Size[find(a)]<<endl;         }     }     return 0; }