AcWing 837. 连通块中点的数量
原题链接
简单
作者:
acwing_陌路
,
2021-08-20 22:05:12
,
所有人可见
,
阅读 232
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int p[N],cnt[N];//规定只有祖宗才能统计节点个数
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
int n,m;
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
p[i] = i;
cnt[i] = 1;//初始时每个都是自己的父节点,并且个数为1
}
while(m --)
{
string op;
int a,b;
cin >> op;
if(op == "C")
{
cin >> a >> b;
int j = find(a),k = find(b);//提前把a合并到b之前的父亲存下来
if(j != k)//题目说a,b可能相等
{
p[j] = k;
cnt[k] += cnt[j];//b的祖宗统计的个数加上a的祖宗统计的个数
}
}
else if(op == "Q1")
{
cin >> a >> b;
if(find(a) == find(b)) puts("Yes");
else puts("No");
}
else
{
cin >> a;
cout << cnt[find(a)] << endl;//输出a的祖宗统计的个数
}
}
return 0;
}