1118 Birds in Forest (25分) [并查集]

并查集有一个比较令人迷惑的地方在于我还没明白程序就给我合并好了

在此处成功地把群体内的father统一了~

set<int> f;
    for(int i=1;i<=bird;i++){
    	f.insert(findFather(i));
    }

#include<bits/stdc++.h>
using namespace std;
const int maxn=10010;
int father[maxn];
int findFather(int a){
    int x=a;
    while(father[x]!=x) x=father[x];
    while(a!=father[a]){
        int z=a;
        father[a]=x;
        a=father[z];
    }
    return x;
}
void Union(int a,int b){
    int fa=findFather(a);
    int fb=findFather(b);
    if(fa!=fb) father[fa]=fb;
}
int main(){
    int n,k;
    cin>>n;
    int bird=0;
    for(int i=0;i<maxn;i++) father[i]=i;
    while(n--){
        int x;cin>>x;
        int a,b;
        if(x>=1){
            cin>>a;
            if(a>bird) bird=a;
        }
        for(int i=1;i<x;i++){
            cin>>b;Union(a,b);
            if(b>bird) bird=b;
        }
    }
    set<int> f;
    for(int i=1;i<=bird;i++){
    	f.insert(findFather(i));
    }
    cout<<f.size()<<" "<<bird<<endl;
    cin>>k;
    int a,b;
    while(k--){
        cin>>a>>b;
        if(father[a]==father[b]) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}