AcWing 837. 连通块中点的数量
原题链接
简单
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N], cnt[N];
int find(int u)
{
if(u != p[u]) p[u] = find(p[u]);
return p[u];
}
int main()
{
string s;
int a, b;
cin >> n >> m;
for(int i = 1; i <= n; i ++)
p[i] = i, cnt[i] = 1;
for(int i = 0; i < m; i ++)
{
cin >> s;
if(s == "C")
{
cin >> a >> b;
// find 函数会使 a 的根节点改变,但后面的操作要用到之前的根节点,所以需要提前存好
int f_a, f_b;
f_a = find(a);
f_b = find(b);
p[f_a] = f_b;
if(f_a != f_b) // 不判断的话,可能会加重复
cnt[f_b] += cnt[f_a];
}
else if(s == "Q1")
{
cin >> a >> b;
if(find(a) == find(b)) cout << "Yes" << endl;
else cout << "No" << endl;
}
else
{
cin >> a;
cout << cnt[find(a)] << endl;
}
}
return 0;
}