并查集模版

#include <stdio.h>
int bin[50010];

int findx(int x)
{
    int r=x;
    while(r!=bin[r])
        r=bin[r];
    int j=x;
    int k;
    while(bin[j]!=r)
    {
       k=bin[j];
       bin[j]=r;
       j=k;
    }
    return r;
}

void merge(int x,int y)
{
    int fx,fy;
    fx = findx(x);
    fy = findx(y);
    if(fx != fy)
        bin[fx] = fy;
}

int main()
{
    int n,m,x,j,y,i,k=0,count;
    bin[0]=0;
    while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
    {
        for(i=1;i<=n;i++)
            bin[i]=i;
        for(j=m;j>0;j--)
        {
            scanf("%d %d",&x,&y);
            merge(x,y);
        }
        for(count=0,i=1;i<=n;i++)
            if(bin[i] == i)
                count ++;
        k++;
        printf("Case %d: %d\n",k,count);

    }
       return 0;
}

#include <stdio.h>
int bin[50010];

int findx(int x)
{
    int r=x;
    while(r!=bin[r])
        r=bin[r];
    int j=x;
    int k;
    while(bin[j]!=r)
    {
       k=bin[j];
       bin[j]=r;
       j=k;
    }
    return r;
}

void merge(int x,int y)
{
    int fx,fy;
    fx = findx(x);
    fy = findx(y);
    if(fx != fy)
        bin[fx] = fy;
}

int main()
{
    int n,m,x,j,y,i,k=0,count;
    bin[0]=0;
    while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
    {
        for(i=1;i<=n;i++)
            bin[i]=i;
        for(j=m;j>0;j--)
        {
            scanf("%d %d",&x,&y);
            merge(x,y);
        }
        for(count=0,i=1;i<=n;i++)
            if(bin[i] == i)
                count ++;
        k++;
        printf("Case %d: %d\n",k,count);

    }
       return 0;
}

并查集模版,布布扣,bubuko.com

并查集模版

原文：http://www.cnblogs.com/zhangmingcheng/p/3667312.html