【PAT甲级】1118 Birds in Forest (25分)(并查集)

时间:2021-08-12 21:28:34

题意:

输入一个正整数N(<=10000),接着输入N行数字每行包括一个正整数K和K个正整数,表示这K只鸟是同一棵树上的。输出最多可能有几棵树以及一共有多少只鸟。接着输入一个正整数Q,接着输入Q行每行包括两个正整数,输出它们是否在同一棵树上。

AAAAAccepted code:

 #define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int fa[];
int vis[];
int find_(int x){
if(x==fa[x])
return x;
return fa[x]=find_(fa[x]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin>>n;
for(int i=;i<=;++i)
fa[i]=i;
for(int i=;i<=n;++i){
int k;
cin>>k;
int temp=;
for(int j=;j<=k;++j){
int x;
cin>>x;
vis[x]=;
int f=find_(x);
if(j==)
temp=f;
fa[f]=temp;
}
}
int cnt=;
int sum=;
for(int i=;i<=;++i)
if(fa[i]==i&&vis[i])
++cnt;
else if(vis[i])
++sum;
cout<<cnt<<" "<<cnt+sum<<"\n";
int q;
cin>>q;
while(q--){
int a,b;
cin>>a>>b;
if(find_(a)==find_(b))
cout<<"Yes\n";
else
cout<<"No\n";
}
return ;
}