AcWing 1608. 森林里的鸟
原题链接
简单
作者:
leo123456
,
2020-08-20 22:18:18
,
所有人可见
,
阅读 515
#include<iostream>
#include<cstring>
#include<unordered_set>
using namespace std;
const int N=100010;
int n,m;
int p[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int cnt=0;
unordered_set<int> s;
int main()
{
cin>>n;
for(int i=1;i<N;i++) p[i]=i;
for(int i=1;i<=n;i++)
{
int k;
cin>>k;
int f1;
cin>>f1;
s.insert(f1);
for(int j=1;j<k;j++)
{
int fn;
cin>>fn;
s.insert(fn);
f1=find(f1),fn=find(fn); 集合合并一定先find.
if(f1!=fn)
{
p[fn]=f1;
cnt++;
}
}
}
cout<<s.size()-cnt<<' '<<s.size()<<endl;
cin>>m;
while(m--)
{
int a,b;
cin>>a>>b;
if(find(a)!=find(b)) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}