易妖游戏网
您的当前位置:首页POJ2524-Ubiquitous Religions

POJ2524-Ubiquitous Religions

来源:易妖游戏网

题目链接:

并查集水题,给出同学数量n,和m组关系,接下来的m组数表示这两个同兄在一个社团,求社团(根)的数量。

//360K	391MS	
//C++	665B
#include <cstdio>
#include <cstring>
#define N 55555
int n,m,s[N],sum;
int main()
{
    int i,n,m,x,y,l=0,sum;
    while(~scanf("%d%d",&n,&m)&&(n||m))
    {
        sum=0;
        for(i=1;i<=n;i++)
        {
            s[i]=i;
        }
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&x,&y);
            while(x!=s[x])
            {
                x=s[x];
            }
            while(y!=s[y])
            {
                y=s[y];
            }
            s[y]=x;
        }
        for(i=1;i<=n;i++)
        {
            if(s[i]==i)
            {
                sum++;
            }
        }
        printf("Case %d: %d\n",++l,sum);
    }
}


因篇幅问题不能全部显示,请点此查看更多更全内容