题目粗心
当初有N张图片，每一张图片外面有K只鸟，在同一张图片中的鸟属于同一棵树，计算森林中树木的最大数目，并且对于任意一对鸟，判断是否在同一棵树上。
算法思路
本题考查并查集的利用，咱们应用set汇合birds保留所有的输出的鸟，并在输出每一张图片的时候，将其中所有的鸟进行合并为一组，而后对于birds中所有的鸟类依据其先人归并为一棵树，并存放到set汇合trees中，最初对于任意两个鸟的编号，只须要比拟father数组的值是否雷同即可。
留神点
- 1、查找father的办法得应用门路压缩，不然会有一个测试点超时。
提交后果
AC代码
#include<cstdio>#include<algorithm>#include<unordered_set>#include<vector>using namespace std;unordered_set<int> birds;unordered_set<int> trees;int father[10005];int findFather(int x){ int a = x; while(x!=father[x]){ x = father[x]; } while (a!=father[a]){ int z = father[a]; father[a] = x; a = z; } return x;}void Union(int a,int b){ int fa = findFather(a); int fb = findFather(b); if(fa!=fb){ father[fa] = fb; }}int main() { for(int i=0;i<=10000;++i){ father[i] = i; } int n; scanf("%d",&n); for(int i=0;i<n;++i){ int k; scanf("%d",&k); vector<int> t(k); for(int j=0;j<k;++j){ scanf("%d",&t[j]); birds.insert(t[j]); if(j!=0){ Union(t[j],t[j-1]); } } } for(auto it:birds){ int f=findFather(it); trees.insert(f); } printf("%lu %lu\n",trees.size(),birds.size()); int query; scanf("%d",&query); for(int i=0;i<query;++i){ int a,b; scanf("%d %d",&a,&b); if(father[a]==father[b]){ printf("Yes\n"); }else{ printf("No\n"); } } return 0;}