POJ1611 The Suspects

    原题链接：http://poj.org/problem?id=1611

    并查集。在每个group中，最开始的出发点是以该group中最小编号的学生为根的（这个是根据题意编号为0的学生是suspect来决定的），如果该group中有某个学生的父亲节点（或祖父节点）编号大于该group最小编号，则将最小编号union到上述的父亲节点（或祖父节点）上，那么在处理完成后，可以构造出一颗以编号0学生为根的树（并查集）。对所有节点询问其祖先节点，如果其祖先节点编号为0，那么计数加1。

#include <stdio.h>
#include <algorithm>
#define N 30010
#define INF 0x3f3f3f3f
int f[N], a[N];

int find(int x)
{
    return x == f[x] ? f[x] : f[x] = find(f[x]);
}

inline void MakeSet()
{
    for(int i = 0; i < N; i ++)
        f[i] = i;
}

int main()
{
    int i, j, k, n, m, cnt;
    while(scanf("%d%d", &n, &m), (n || m))
    {
        MakeSet();
        while(m --)
        {
            scanf("%d", &k);
            for(i = 0; i < k; i ++)
                scanf("%d", &a[i]);
            std::sort(a, a + k);
            for(i = 1; i < k; i ++)
            {
                j = f[a[i]]; 
                if(j != a[i])   // 如果条件成立，那么a[i]已经属于某棵树
                {
                    if(f[j] < f[a[0]])   // a[i]的元祖先与当前祖先比较，将较大的祖先合并到较小的祖先
                        f[a[0]] = f[j];
                    else
                        f[j] = f[a[0]];
                }
                else
                    f[a[i]] = f[a[0]];
            }
        }
        for(cnt = i = 0; i <= n; i ++)
        {
            j = find(i);
            if(j == 0)
                cnt ++;
        }
        printf("%d\n", cnt);
    }
    return 0;
}