并查集

#include <stdio.h>

#define SIZE 30001
int p[SIZE];
int rank[SIZE];
int num[SIZE]; //record total number of current set


void makeSet(int x)
{
    rank[x] = 0;
    p[x] = x;
    num[x] = 1;
}

int findSet(int x)
{
    if(x != p[x])
        p[x] = findSet(p[x]);
    return p[x];
}

void unionSet(int x, int y)
{
    int px, py;

    px = findSet(x);
    py = findSet(y);

    if(px == py)
        return;

    if(rank[px] > rank[py])
    {
        p[py] = px;
        num[px] += num[py];
    }
    else
    {
        p[px] = py;
        num[py] += num[px];
        if(rank[px] == rank[py])
            rank[py]++;
    }
}

int main(void)
{
    int n, m, k, i, j, u, v;

    while(scanf("%d%d", &n, &m) && (n || m))
    {
        for(i = 0; i < n; i++)
            makeSet(i);

        if(0 == m)
            goto done;

        for(i = 0; i < m; i++)
        {
            scanf("%d", &k);
            for(j = 0; j < k; j++)
            {
                scanf("%d", &v);
                if(j > 0)
                    unionSet(u, v);
                u = v;
            }
        }

done:
        printf("%d\n", num[findSet(0)]);
    }

    return 0;
}