并查集（模板&典型例题整理）

参考：

带路径压缩模板：

#include<stdio.h>
int father[1005];
int Find(int x)
{

    if(x!=father[x])//注意这里是if不是while！ 
        father[x]=Find(father[x]);
    return father[x];    
}
void Combine(int a,int b)
{
    int fa=Find(a);
    int fb=Find(b);
    if(fa!=fb)
    {
        father[fa]=fb;
    }
}
int main()
{
//    freopen("in.txt","r",stdin);
    int n,m;
    int i;
    int a,b;
    while(~scanf("%d",&n))
    {
        if(n==0)
        break;
        scanf("%d",&m);
        int sum=0;
        for(i=1;i<=n;i++)
            father[i]=i;
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            Combine(a,b);
        }
        for(i=1;i<=n;i++)
        {
            if(father[i]==i)
                sum++;    
        }    
        printf("%d\n",sum-1);
    }
    return 0;
}