图论-并查集模版

#include<stdio.h>

int father[1005];


int find(int x)
{
    int r=x;
    while(father[r]!=r)
    {//沿着关系一直向上摸索
        r=father[r];
    }
    int i=x,k;
    //压缩
    while(i!=r)
    {//若直接上级不是最终老大
        k=father[i];
        father[i]=r;//就直接与老大相连
        i=k;
    }
    return r;
}


void merge(int x,int y)
{
    int fx,fy;
    fx=find(x);//找x的老大
    fy=find(y);
    if(fx!=fy)//是否同一个老大
    {
        father[fx]=fy;//fy做fx的老大
    }
}


int main()
{
    int n,m,i;
    while(scanf("%d",&n)!=EOF,n)
    {
        scanf("%d",&m);
        for(i=0;i<=n;i++)
            father[i]=i;
        while(m--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(a>b)
                merge(a,b);
            else
                merge(b,a);
        }
        int ans=0;
        for(i=1;i<=n;i++)
            if(father[i]!=i)
                ans++;
        printf("%d
",n-ans-1);
    }

    return 0;
}