题解：UVA1197 The Suspects

UVA1197 The Suspects

题目大意

有某种传染性很强的神秘疾病在某校学生中传播。学校里有若干团体，只要有一人是“密接”，那么团体内的其他所有人都是“密接”。一个学生可能属于多个团体。现给出学校内所有团体的成员信息，并已知学生 $0$ 是“密接”，求校内“密接”的个数。

解题思路

可以说是并查集的模板题。每次将一个团体内的同学的所在组合并，最后检查和 $0$ 在一组的同学个数即为答案。

参考代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <numeric>
#include <vector>
// #include<unordered_map>
// #define map unordered_map
#ifdef ONLINE_JUDGE
#    define getchar getchar_unlocked
#endif
using namespace std;
/*================*/

inline int read() {
    char c = getchar();
    int  x = 0, f = 1;
    for (; !isdigit(c); c = getchar())
        if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    return x * f;
}

#define r(a) (a) = read()

#define MAXN 30005
#define MAXM 505

int n, m, x, u, ans;
int fa[MAXN];

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

signed main() {
	while (1) {
		r(n); r(m);
		if (!(m + n))
			break;
		iota(fa, fa + n, 0);
		ans = 0;
		while (m--) {
			int cnt = read();
			r(x);
			cnt--;
			int root = find(x);
			while (cnt--) {
				r(x);
				u = find(x);
				if (u == root)
					continue;
				fa[u] = root;
			}
		}
		int targ = find(0);
		for (int i = 0; i < n; i++)
			if (find(i) == targ)
				ans++;
		printf("%d\n", ans);
	}
	return 0;
}