AcWing 837. 连通块中点的数量
原题链接
简单
作者:
时过境迁
,
2021-02-03 19:08:19
,
所有人可见
,
阅读 266
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int p[N], si[N];
int n, m;
/**
初始化
图中没有变,所有每个节点都是一个连通块,同时该连通块个数为1
*/
void init()
{
for(int i = 1; i <= n; ++i)
{
p[i] = i;
si[i] = 1; //该数组以后只对连通块的祖先节点开放权限
}
}
/**
找到该节点的连通块的祖先节点+路径压缩
*/
int find(int x)
{
if(p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int main()
{
cin>>n>>m;
init(); //初始化
char op[2];
int a, b;
while(m--)
{
cin>>op;
if(op[0] == 'C')
{
cin>>a>>b;
if(find(a) == find(b)) //如果节点a与节点b所在同一个连通块
continue;
//反之,约定使a所在连通块的祖先节点 的父节点为节点b所在连通块的祖先节点
//同时要更新节点b连通块的节点数
si[find(b)] += si[find(a)]; //顺序不能颠倒
p[find(a)] = find(b);
}
else if(op[1] == '1')
{
cin>>a>>b;
if(find(a) == find(b))
puts("Yes");
else
puts("No");
}
else
{
cin>>a;
cout<<si[find(a)]<<endl;
}
}
return 0;
}