【POJ】[2524]Ubiquitous Religions

POJ终于恢复了……
喜大普奔

这一题也算是标准的并查集了
不多说了……

#include<stdio.h>
int par[50050];
int rank[50050];
int find(int m) {
    if(par[m]==m)
        return m;
    else {
        return par[m]=find(par[m]);
    }
}
void unite(int x,int y) {
    x=find(x);
    y=find(y);
    if(x==y)
        return;
    else {
        if(rank[x]<rank[y]) {
            par[x]=y;
        } else {
            par[y]=x;
            if(rank[x]==rank[y]) {
                rank[x]++;
            }
        }
    }
}
int main() {
    int n,m;
    int kase=0;
    while(scanf("%d %d",&n,&m),n!=0||m!=0) {
        for(int i=1; i<=n; i++) {
            par[i]=i;
            rank[i]=0;
        }
        while(m--) {
            int i,j;
            scanf("%d %d",&i,&j);
            unite(i,j);
        }
        int cnt=0;
        for(int i=1; i<=n; i++) {
            if(par[i]==i)
                cnt++;
        }
        printf("Case %d: %d
",++kase,cnt);
    }
    return 0;
}

题目地址:【POJ】[2524]Ubiquitous Religions