AcWing 837. 连通块中点的数量
原题链接
简单
作者:
时过境迁
,
2021-01-27 15:57:39
,
所有人可见
,
阅读 289
代码两行顺序影响答案
样例
#include <cstdio>
#include <iostream>
using namespace std;
int n, m;
const int N = 100010;
int p[N], si[N];
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void init()
{
for(int i = 1; i <= n; ++i)
{
p[i] = i;
si[i] = 1; //每个点都是一个连通块,故一个连通块只有一个点
//以后只保证根节点的size 有意义
}
}
int main()
{
cin>>n>>m;
init();
while(m--)
{
char op[2];
int a, b;
scanf("%s", op);
if(op[0] == 'C')
{
cin>>a>>b;
if(find(a) == find(b))
continue;
si[find(b)] += si[find(a)]; //该行与下一行一定不可以颠倒,否则,si[b] += 2*si[a];
p[find(a)] = find(b); //a所在连通块指向b
// si[find(b)] += si[find(a)];
}
else if(op[1] == '1')
{
cin>>a>>b;
if(find(a) == find(b))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
else
{
cin>>a;
cout<<si[find(a)]<<endl;
}
}
return 0;
}