UVa 10583 Ubiquitous Religions

7772759      10583      Ubiquitous Reli...      poao899      Accepted      C++      0.152      2010-02-23 13:53:33                                          .


看到Lucky Cat上面分類是少見的disjoint set就來寫了

唔竟然是空虛題orz



//*******************************************************

#include<stdio.h>
#define MAX 50010
int root[MAX],caseCnt,cnt,n,m,a,b;
bool used[MAX];
int find(int a){
    return a==root[a]?a:root[a]=find(root[a]);
}
int main(){
    while(scanf("%d%d",&n,&m),n,m){
        //Init
        for(int i=1;i<=n;i++){
            root[i]=i;
            used[i]=0;
        }
        cnt=0;
        //Input
        while(m--){
            scanf("%d%d",&a,&b);
            root[find(a)]=find(b);
        }
        //Count
        for(int i=1;i<=n;i++)
            if(!used[find(i)]){
                used[root[i]]=1;
                cnt++;
            }
        //Output
        printf("Case %d: %d\n",++caseCnt,cnt);
    }
}