poj 1611(并查集)

http://poj.org/problem?id=1611

题意：有个学生感染病毒了，只要是和这个学生接触过的人都会感染，而和这些被感染者接触的人，也会被感染，现在给定你一些协会的人数，以及所在学生的编号，要你求被感染的人数。

思路：首先，把同一个社团的人，合并到一个这个社团的第一个人的那里，并用一个数组记录这个集合有多少人，最后查找0这个元素在哪个集合就可以。

#include <stdio.h>
#include <string.h>
#define l 30005

int belg[l],num[l];

int Find(int x)
{
    int _x=x,_b;
    while(_x!=belg[_x])
    {
        _x=belg[_x];
    }
    while(x!=belg[x])
    {
        _b=belg[x];
        belg[x]=_x;
        x=_b;
    }
    return _x;
}

void unio (int x,int y)
{
    int root1=Find(x);
    int root2=Find(y);
    if(root1!=root2)
    {
        belg[root1]=root2;
        num[root2]+=num[root1];    //合并的时候，记得把人数也合并。
    }
}

int main()
{
    int m,n,a,b,c;
  //  freopen("in.txt","r",stdin);
    while(scanf("%d%d",&m,&n))
    {
        if(m==n&&m==0) break;
        if(m==0) printf("1
");
        for(int i=0;i<m;i++)
        {
            belg[i]=i;
            num[i]=1;
        }
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            for(int i=1;i<a;i++)
            {
                scanf("%d",&c);
                unio(b,c);
                b=c;
            }
        }
        printf("%d
",num[Find(0)]);
    }
    return 0;
}