原题目:森林里的鸟
https://www.acwing.com/solution/content/184005/
并查集模板包含两部分,find和merge,find包含了路径压缩,merge包含了启发式合并。
启发式合并需要一个sz数组用于判断以它为根节点的子树深度。
#include <iostream>
#include <unordered_set>
using namespace std;
const int N = 1e5 + 10;
int p[N], s[N];
int n;
unordered_set<int> birds, tr;
int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
void merge(int x, int y) {
int a = find(x), b = find(y);
if (a == b)return;
if (s[a] < s[b])swap(a, b);
p[b] = a;
s[a] += s[b];
}
int main() {
for (int i = 0; i < N; i++) {
p[i] = i;
s[i] = 1;
}
cin >> n;
while (n--) {
int k, b, t;
cin >> k >> b;
birds.insert(b);
for (int i = 1; i < k; i++) {
cin >> t;
merge(b, t);
birds.insert(t);
}
}
int q;
cin >> q;
for (auto it = birds.begin(); it != birds.end(); it++) {
if (tr.find(*it) == tr.end()) {
tr.insert(find(*it));
}
}
cout << tr.size() << ' ' << birds.size() << '\n';
while (q--) {
int x, y;
cin >> x >> y;
if (find(x) == find(y))
cout << "Yes\n";
else cout << "No\n";
}
}