PAT甲级1118 Birds in Forest ：[C++题解]并查集

文章目录

• • 题目分析
  • 题目链接

题目分析

来源：acwing
分析：并查集的合并和查询。

问：一张照片上的鸟如何合并？相邻的合并（笔者采用的方式）或者全合并到第一只鸟就行，遍历一遍。所有照片中的鸟，合并的次数累加到变量cnt中。

问：如何统计鸟的数量？用一个bool数组，出现过的置为true。遍历一遍统计true的个数就是所有的鸟的数量total。

问：如何统计树的数量？首先说一点，total是鸟的数量，初始化的时候每只鸟是一个独立的集合。树的数量是total - cnt。为什么是这个公式？这个道理就相当于，有3个集合，合并2个，还剩几个集合？当然还剩1个啦。

树的数量 = 鸟的数量 - 合并的次数 比如 照片1：1 2 3 照片2： 2 4 5 照片3：7 8 9 这个例子中，树的数量是2棵，是怎么求的？ 过程如下： 总共鸟数total =8， 3张照片总共合并次数cnt=2+2+2 =6， 得出，树的数量= total -cnt =2。

ac代码

#include<bits/stdc++.h> using namespace std;const int N = 1e4+10; unordered_set<int> S[N];int n; int p[N]; int birds[11]; //每张照片的鸟先存下来 bool st[N]; int find(int x){if(p[x] != x) p[x] = find(p[x]);return p[x]; }int main(){cin >> n;//初始化所有的鸟，每只鸟都是一个集合for(int i =1; i<N; i++) p[i] = i;//统计合并了多少次cntint cnt = 0;for(int i = 1; i<= n; i ++){int k;cin >>k;for(int j =0; j<k; j++) {cin >> birds[j];st[birds[j]] =true; //表示这只鸟存在一个集合中}//合并一张照片中的鸟//相邻的合并：前面的合并到后面的//从前往后枚举一遍，就合并完成为1个集合for(int j = 1; j<k; j++){int a = birds[j-1],b=birds[j];a = find(a),b = find(b);if(a != b){p[a] =b;cnt ++; } }}//统计所有的鸟的只数int total = 0;for(int i = 0; i<N;i ++) total += st[i];//树的数量 = 鸟的数量 - 合并的次数//比如 照片1：1 2 3 照片2： 2 4 5 照片3：7 8 9这个例子：树的数量：2棵//怎么求的？ 总共鸟数total =8， 3张照片总共合并次数cnt=2+2+2 =6，树的数量= total -cnt =2cout<< total -cnt <<" "<<total<<endl;int q;cin >> q;while(q--){int a, b;cin >> a >> b;if(find(a) == find(b)) cout<<"Yes"<<endl;else cout<<"No"<<endl;} }

题目链接

PAT甲级1118 Birds in Forest
https://www.acwing.com/problem/content/1610/

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的PAT甲级1118 Birds in Forest ：[C++题解]并查集的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。