题目描述
AC代码
#include<bits/stdc++.h>
using namespace std;
int father[10005];
int find(int x){while(father[x]>=0){x=father[x];}return x;
}
void Union(int a,int b){int fa=find(a),fb=find(b);if(fa!=fb){ //按秩归并 if(father[fa]<father[fb]){father[fa]+=father[fb];father[fb]=fa;}else{father[fb]+=father[fa];father[fa]=fb;}}
}
int main() {memset(father,-1,sizeof(father)); //注意初始化 int n,maxnum=0;cin>>n;while(n--){int k,root,temp;cin>>k;for(int i=0;i<k;i++){scanf("%d",&temp);maxnum=max(maxnum,temp); //更新birds id的最大值 if(i==0) root=temp; //将每张图片的第一只bird作为根结点 else Union(temp,root);}}int cnt=0,num=0;for(int i=1;i<=maxnum;i++){if(father[i]<0) {cnt++; //集合个数 num-=father[i]; //number of birds}}printf("%d %d\n",cnt,num);int k;cin>>k;while(k--){int a,b;scanf("%d%d",&a,&b);printf("%s\n",find(a)==find(b)?"Yes":"No");}return 0;
}