AcWing 837. 连通块中点的数量
原题链接
简单
题目描述
样例
#include <iostream>
using namespace std;
const int N=100010;
int p[N];//存储节点的父节点
int s[N];//记录节点的数量,只需要维护根节点size既可,找到根节点x返回size[a]就是集合中所有结点的数量(还要注意的一点是这里不能用size会引起冲突)
int n,m;
int find(int x){//返回节点x的祖宗节点+路径优化
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
p[i]=i;
s[i]=1;
} //刚开始每个结点在一个集合中,所以每个集合中点的数量为1
while(m--){
char op[5];
int a,b;
cin>>op;
if(op[0]=='C'){//合并
cin>>a>>b;
if(find(a)==find(b)) continue;
s[find(b)]+=s[find(a)];
p[find(a)]=find(b);
}
if(op[1]=='1'){
cin>>a>>b;
if(find(a)==find(b)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
if(op[1]=='2'){
cin>>a;
cout<<s[find(a)]<<endl;
}
}
return 0;
}