AcWing 837. 连通块中点的数量
原题链接
简单
连通块中点的数量
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int p[N], _size[N];
void init(int n) {
for (int i = 1; i <= n; i++) {
p[i] = i;
_size[i] = 1;
}
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
bool connected(int a, int b) {
return find(a) == find(b);
}
void merge(int a, int b) {
if (find(a) == find(b)) {
return;
} else { // 这两句不可交换顺序!
_size[find(b)] += _size[find(a)];
p[find(a)] = find(b);
}
}
int count(int x) {
return _size[find(x)];
}
/**
* acwing 837-连通块的个数
* @return
*/
int main() {
int n, m;
cin >> n >> m;
init(n);
string op;
int a, b;
while (m--) {
cin >> op;
if (op == "C") {
cin >> a >> b;
merge(a, b);
} else if (op == "Q1") {
cin >> a >> b;
cout << (connected(a, b) ? "Yes" : "No") << endl;
} else if (op == "Q2") {
cin >> a;
cout << count(a) << endl;
}
}
return 0;
}