PAT甲级 1118 Birds in Forest 并查集

代码如下：

//并查集
#include<iostream>
#include<vector>
#include<stdio.h>
#include<math.h>
#define MAX 10005
using namespace std;

int fa[MAX];
int n,k,q;
int flag[MAX]={0};

int findfather(int x){
    if(x!=fa[x]){
        return findfather(fa[x]);
    }else{
        return fa[x];
    }
}

void _union(int a,int b){
    int aa=findfather(a);
    int bb=findfather(b);
    if(aa!=bb){
        fa[aa]=bb;
    }
}

int main(){
    for(int i=0;i<10005;i++){
        fa[i]=i;
    }
    scanf("%d",&n);
    int cnt=0;//记录集合数
    int num=0;//记录鸟的数目
    int id,temp,maxl=0;
    for(int i=0;i<n;i++){
        scanf("%d%d",&k,&id);
        if(flag[id]==0){
            flag[id]=1;
            num++;
            maxl=max(maxl,id);
        }
        for(int j=0;j<k-1;j++){
            scanf("%d",&temp);
            _union(id,temp);
            if(flag[temp]==0){
                flag[temp]=1;
                num++;
            }
            maxl=max(maxl,temp);
        }
    }

    for(int i=1;i<=maxl;i++){
        if(i==fa[i]){
            cnt++;
        }
    }
    printf("%d %d\n",cnt,num);
    scanf("%d",&q);
    int a,b;
    for(int i=0;i<q;i++){
        scanf("%d%d",&a,&b);
        if(findfather(a)!=findfather(b)){
            printf("No\n");
        }else{
            printf("Yes\n");
        }
    }
    return 0;
}