(并查集)The Suspects --POJ --1611

链接:

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

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82830#problem/B

代码:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define N 30005

int a[N];
int n, m;

int Find(int x)
{
    if(a[x]!=x)
        a[x] = Find(a[x]);
    return a[x];
}

int main()
{

    while(scanf("%d%d", &n, &m), n+m)
    {
        int p, px, py, s, x, y;

         for(int i=0; i<=n; i++)
            a[i] = i;

        for(int i=0; i<m; i++)
        {
            scanf("%d%d", &s, &x);

            for(int j=1; j<s; j++)
            {
                scanf("%d", &y);

                px = Find(x);
                py = Find(y);
                if(px!=py)
                    a[py] = px;
            }
        }
        int sum=0;
        p = Find(0);

         for(int i=0; i<n; i++)
            if(Find(i)==p)
            sum++;

         printf("%d
", sum);

    }
    return 0;
}