AcWing 837. 连通块中点的数量
原题链接
简单
作者:
为了樱岛麻衣
,
2023-01-11 13:04:56
,
所有人可见
,
阅读 111
#include<iostream>
using namespace std;
const int N = 1e5+10;
int fa[N], cnt[N];
// 找到祖宗节点
int find(int x)
{
if(fa[x] != x) fa[x] = find(fa[x]); // 递归查找,并进行路径压缩,也就是把路过的节点全部插到祖宗节点上
return fa[x];
}
// 合并操作直接将 x 的祖宗节点插到 y 上
void un(int x, int y)
{
// 特判, 两个节点属于不同集合才将点数加入
if(find(x) != find(y))
{
cnt[find(y)] += cnt[find(x)];
}
fa[find(x)] = find(y);
}
int main()
{
int n, m;
cin >> n >> m;
// 进行初始化, 没有0号节点,所以从1开始
for(int i = 1; i <= n; i++)
{
fa[i] = i;
cnt[i] = 1;
}
while(m--)
{
string op;
int a, b;
cin >> op;
if(op == "C")
{
scanf("%d%d", &a,&b);
un(a, b);
}
else if(op == "Q1")
{
scanf("%d%d", &a, &b);
// 祖宗节点相同说明是同一个集合
printf("%s\n", find(a) == find(b) ? "Yes" : "No");
}
else
{
scanf("%d", &a);
printf("%d\n", cnt[find(a)]);
}
}
return 0;
}