【1118】Birds in Forest (25 分)

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>  
#include<map>
#include<vector>
#include<queue> 
using namespace std;  
//key:并查集，注意不同照片可能是同一棵树==
//exist[i]表示鸟的id---i在输入的鸟的序号里面是否出现过
//cnt[i]数组保存以i为FindFather结点的集合里鸟的个数
int n,m,k;
const int maxn=10010;
int father[maxn]={0},cnt[maxn]={0};
//cnt[i]数组保存以i为FindFather结点的集合里鸟的个数
int  findFather(int x){  //查找x所在集合的根结点
  int a=x;
  while(x != father[x]){
    x=father[x];
  }
  //路径压缩
  while(a !=father[a]){ 
    int z=a;
    a=father[a];
    father[z]=x;
  }
  return x;
}
void Union(int a,int b){ //合并a和b所在的集合
  int faA=findFather(a);
  int faB=findFather(b);
  if(faA != faB){
    father[faA]=faB;
  }
}
bool exist[maxn];
//exist[i]表示鸟的id---i在输入的鸟的序号里面是否出现过
int main(){   
  scanf("%d",&n);
  for(int i=1;i<=maxn;i++)
    father[i]=i;
  int id,temp;
  for(int i=0;i<n;i++){
    scanf("%d%d",&k,&id);//id为此画第一只鸟
    exist[id]=true;
    for(int j=0;j<k-1;j++){//遍历剩下的k-1只鸟
      scanf("%d",&temp);
      Union(id,temp);//并
      exist[temp]=true;
    }
  }
  for(int i=1;i<=maxn;i++){
    if(exist[i]==true){
      int root=findFather(i);
      cnt[root]++;
      //cnt[i]数组保存以i为FindFather结点的集合里鸟的个数
    }
  }
  int numTrees=0,numBirds=0;
  for(int i=1;i<=maxn;i++){
    if(exist[i] == true&& cnt[i] != 0){//前者省去也可ac
      numTrees++;
      numBirds+=cnt[i];
    }
  }
  printf("%d %d\n",numTrees,numBirds);
  scanf("%d",&m);
  int ida,idb;
  for(int i=0;i<m;i++){
    scanf("%d%d",&ida,&idb);
    printf("%s\n",(findFather(ida) == findFather(idb)) ? "Yes": "No");//学习此写法
  }
  system("pause");
    return 0;   
}