POJ 2524 独一无二的宗教（裸并查集）

#include<stdio.h>
#include<iostream>
using namespace std;
#define max_v 50005
int pa[max_v];//pa[x] 表示x的父节点
int rk[max_v];//rk[x] 表示以x为根结点的树的高度
int n,ans;
void make_set(int x)
{
    pa[x]=x;
    rk[x]=0;//一开始每个节点的父节点都是自己
}
int find_set(int x)//带路径压缩的查找
{
    if(x!=pa[x])
        pa[x]=find_set(pa[x]);
    return pa[x];
}
void union_set(int x,int y)
{
    x=find_set(x);//找到x的根结点
    y=find_set(y);
    if(x==y)//根结点相同 同一棵树
        return ;
    ans--;
    if(rk[x]>rk[y])
    {
        pa[y]=x;
    }else
    {
        pa[x]=y;
        if(rk[x]==rk[y])
            rk[y]++;
    }
}
int main()
{
    int n,m,j=0;
    while(~scanf("%d %d",&n,&m))
    {
        if(m+n==0)
            break;
        for(int i=1;i<=n;i++)
        {
            make_set(i);
        }
        ans=n;
        for(int i=0;i<m;i++)
        {
            int x,y;
            scanf("%d %d",&x,&y);
            union_set(x,y);
        }
        printf("Case %d: %d\n",++j,ans);
    }
    return 0;
}