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

本文主要是介绍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;}
}