PAT A1118 Birds in Forest [并查集]

题目描述

链接
一幅画里面的鸟为同一棵树上的，问有多少棵树和多少只鸟，以及对于两只鸟判断是否在同一个树上

分析

• 如何合并: 枚举(1)到(k), (merge(0, x))

• 统计信息：(fa[i]=i,i=1..maxn)执行初始化, (vis[i]) 来标注有效结点，用(cnt[])记录集合中元素个数, (cnt[find(i)]++)

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e4+5;
int fa[maxn];
int find(int x){
    int r = x;
    while(x!=fa[x]) x=fa[x];
    while(r!=fa[r]){
        int t = r;
        r = fa[r];
        fa[t] = x;
    }
    return x;
}
void merge(int x, int y){
    fa[find(x)] = find(y);
}
void init(){
    for(int i=0;i<maxn;i++) fa[i] = i;
}
int n,k,a[maxn];
bool vis[maxn];
int cnt[maxn];
int main(){
    init();
    scanf("%d",&n);
    while(n--){
        scanf("%d",&k);
        for(int i=0;i<k;i++){
            scanf("%d",&a[i]);
            vis[a[i]] = true;
        }
        for(int i=1;i<k;i++){
            merge(a[0],a[i]);
        }
    }
    for(int i=0;i<maxn;i++){
        if(vis[i]){
            int root = find(i);
            cnt[root]++;
        }
    }
    int numTrees = 0, numBirds = 0;
    for(int i=0;i<maxn;i++){
        if(cnt[i]){
            numTrees++;
            numBirds += cnt[i];
        }
    }
    printf("%d %d
",numTrees, numBirds);
    scanf("%d",&n);
    for(int k=0;k<n;k++){
        int i,j;
        scanf("%d%d",&i,&j);
        if(find(i)==find(j)) printf("Yes
");
        else printf("No
");
    }
}