学步园

题意:

有n个学生,m对样本.每对样本x,y表示编号为x,y(从1开始)的学生有相同的宗教信仰.

问n个学生共涉及多少个不同的宗教.

裸并查集...

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 50005;
int set[MAXN];//father or -num

void Init(void)
{
    memset(set,-1,sizeof(set));
}

int Find(int x)
{
    if(set[x]<0)    return x;
    else
    {
        set[x] = Find(set[x]);
        return set[x];
    }
}

void Union(int root1,int root2)
{
    int a = Find(root1),b = Find(root2);
    if(a==b) return;
    if(set[a]<set[b])
    {
        set[a] += set[b];
        set[b] = a;
    }
    else
    {
        set[b] += set[a];
        set[a] = b;
    }
}
//360K	297MS
int main()
{
    int Case = 1,n,m;
    while(scanf("%d%d",&n,&m)!=EOF&&(n+m))
    {
        Init();
        for(int i=0;i<m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            Union(x,y);
        }
        int cnt = 0;
        for(int i=1;i<=n;i++)
            if(set[i]<0) cnt++;
        printf("Case %d: %d\n",Case++,cnt);
    }
    return 0;
}