AcWing 837. 连通块中点的数量
原题链接
简单
作者:
王小强
,
2021-01-24 13:25:47
,
所有人可见
,
阅读 239
并查集课后作业
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int p[N], counts[N];
// path compression
int Find(const int x) {
return p[x] ^ x ? p[x] = Find(p[x]) : x;
}
int isConnected(const int a, const int b) {
return Find(a) == Find(b);
}
void Union(const int a, const int b) {
if (a == b) return;
const int pa = Find(a);
const int pb = Find(b);
if (pa == pb) return;
p[pa] = pb;
counts[pb] += counts[pa];
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i)
p[i] = i, counts[i] = 1;
while (m--) {
string op;
int a, b;
cin >> op;
if (op == "C") {
cin >> a >> b;
Union(a, b);
} else if (op == "Q1") {
cin >> a >> b;
puts(isConnected(a, b) ? "Yes" : "No");
} else {
cin >> a;
cout << counts[Find(a)] << endl;
}
}
return 0;
}