题意

2019冠状病毒病（英语：Coronavirus disease 2019，缩写：COVID-19 ），是一种由严重急性呼吸系统综合症冠状病毒2型（缩写：SARS-CoV-2）引发的传染病。此病在全球各国大规模爆发并急速扩散，成为人类历史上致死人数最多的流行病之一。 很显然，目前最好的办法就是将所有可能的患者都隔离起来。 现在某高校正在排查可能的患者，这个高校中有多个社团，每个社团经常进行内部交流，一名学生可能会加入多个社团。学校认为一旦某个社团里出现一名可疑患者，这整个社团的学生都被视为是可能的患者。 现在请你帮忙找到这所学校的所有可能的患者。

（题面漏了一句话：0号学生带病毒。）

输入格式

输入文件包含多组数据。

对于每组测试数据：

第一行为两个整数n和m, 其中n是学生的数量, m是社团的数量。0 < n <= 30000，0 <= m <= 500。

接下来m行，每一行有一个整数k，代表社团中学生的数量。之后，有k个整数代表这个社团里每个学生的编号（在0到n-1之间）。

n = m = 0表示输入结束，不需要处理。

输出格式

对于每组测试数据， 输出可能的患者数目。

样例

Input Output
100 4 2 1 2 5 11 13 50 12 14 2 0 1 2 99 2 200 2 1 5 6 5 6 7 8 9 10 1 0 0 0 4 1 1

思路

并查集模板题。
用0号学生做根节点，用数组size[]维护树的节点个数即可，0号学生记录的size就是答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstring>

using namespace std;

const int N = 30010;

int n, m, k;
int p[N], size[N];
int pre, cur;

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

int main() {
    while (~scanf("%d%d", &n, &m) && !(!n&&!m)) {
        memset(p, 0, sizeof p), memset(size, 0, sizeof size);
        for (int i = 0; i < n; i ++ ) p[i] = i, size[i] = 1;

        for (int i = 0; i < m; i ++ ) {
            scanf("%d", &k);
            if (!k) continue;
            scanf("%d", &cur);

            for (int j = 1; j < k; j ++ ) {
                pre = cur;
                scanf("%d", &cur);

                if (j) {
                    if (find(pre) == find(cur)) continue;

                    size[find(pre)] += size[find(cur)];
                    p[find(cur)] = find(pre);
                }
            }
        }

        printf("%d\n", size[find(0)]);
    }

    return 0;
}