The Suspects POJ - 1611 （并查集）

题意：n个学生分属m个团体，一个学生可以属于多个团体。一个学生疑似患病则它所属的整个团体都疑似患病。已知0号学生疑似患病，以及每个团体都由哪些学生构成，求一共多少个学生疑似患病。

分析：维护一个并查集，查询与0在同一集合的元素数量。

#include <iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
const int N = 3010, INF = 0x3f3f3f3f;
int n, m, k;

int f[N];
int find(int u) {
    return u == f[u] ? u : f[u] = find(f[u]);
}
int main() {
    while (~scanf("%d%d", &n, &m) && (n + m != 0)) {
        for (int i = 0; i <= n; i++) f[i] = i;
        for (int i = 1; i <= m; i++) {
            scanf("%d", &k);
            for (int j = 1, u, v; j <= k; j++) {
                scanf("%d", &v);
                if (j > 1) {
                    int fu = find(u), fv = find(v);
                    if (fu != fv) f[fv] = fu;
                }
                u = v;
            }
        }
        int ans = 0, rt=find(0);
        for (int i = 0; i < n; i++)
            if (find(i) == rt) ans++;
        printf("%d\n", ans);
    }
    return 0;
}