1608森林的鸟——并查集acwing

题目：

1608. 森林里的鸟 - AcWing题库

 

分析

使用根存储每个集合的个数（根是p[x]==x) ，使用二维动态数组存储鸟的数据。

使用maxNum来找连续编号中的最大编号，通过p[x]==x统计集合个数

集合两两合并。

其中vector<int> a[N]  可以改成vector<vector<int>> a; a.resize(n+1);

代码

#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10;
int p[N], cnt[N]; int find(int x) {if(p[x]!=x) p[x] = find(p[x]);return p[x];
}int n;
vector<int> v[N];
//int uni[N];
int maxNum;int main() {cin >> n;for(int i = 1; i < N; i ++) p[i]=i, cnt[i]=1;for(int i = 0; i < n; i ++) {int k;cin >> k;for(int j = 0; j < k; j ++) {int t; cin >> t;maxNum = max(t,maxNum);v[i].push_back(t);}
//单独一只鸟自成集合。如果这只鸟属于其他集合，也早已处理过了，不用担心。for(int j = 0; j < v[i].size()-1; j ++) {int a = v[i][j], b = v[i][j+1];a = find(a), b = find(b);if(a!=b) {p[a] = b;cnt[b] += cnt[a];}}}int ans = 0;for(int i = 1; i <= maxNum; i ++) {if(find(i)==i) ans ++;}cout << ans << " " << maxNum << endl;int q;cin >> q;while(q --) {int a,b;cin >> a >> b;if(find(a)==find(b)) puts("Yes");else puts("No");}return 0;
}