POJ 1611 The Suspects（简单并查集）

(￣▽￣)"

#include<iostream>
#include<cstdio>
using namespace std;
int fa[30010];

void makeSet(int n) //初始化，n个元素，处于单独集合
{
    for(int i=0;i<n;i++)
        fa[i]=i;
}

int findSet(int x) //找到该点的粑粑
{
    return fa[x]=fa[x]==x?x:findSet(fa[x]);
}

void unionSet(int x,int y) //粑粑相同的合并成过一个集合
{
    int a=findSet(x),b=findSet(y);
    if(a!=b)
        fa[b]=a;
}

int main()
{
    int n,m,k,g[30010];
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0) break;
        makeSet(n);
        for(int i=0;i<m;i++)
        {
            scanf("%d",&k);
            for(int j=0;j<k;j++)
                scanf("%d",&g[j]);
            for(int j=1;j<k;j++)
                unionSet(g[j-1],g[j]);
        }
        int sum=0;
        for(int i=0;i<n;i++)
        {
            if(findSet(fa[0])==findSet(fa[i]))
                sum++;
        }
        printf("%d
",sum);
    }
    return 0;
}