传染病

COVID-19传染病

问题描述

如果一个感染者走入一个群体，那么这个群体需要被隔离。
小A同学被确诊为新冠感染，并且没有戴口罩！
需要尽快找到所有和小A同学直接或者间接接触过的同学，将他们隔离，防止更大范围的扩散。
众所周知，学生的交际可能是分小团体的，一位学生可能同时参与多个小团体内。

Input

多组数据，对于每组测试数据：
第一行为两个整数n和m（n = m = 0表示输入结束，不需要处理），n 是学生的数量，m 是学生群体的数量。0 < n ≤ 30000 ， 0 ≤ m ≤ 500
学生编号为0~ n-1
小A编号为0
随后，m 行，每行有一个整数 num 即小团体人员数量。随后有 num 个整数代表这个小团体的学生。

Output

输出要隔离的人数，每组数据的答案输出占一行

Sample

Input: 
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0

Output: 
4
1
1

Limitation

Time limit		1000 ms
Memory limit	20000 kB

解题思路

并查集：并：合并两个集合，将元素A作为元素B的父节点；查：确定两个元素是否属于同一集合，每次查找当前节点的父节点，直到遇到根节点，如果两个元素的根节点相同，则它们属于同一集合。

初始化每个成员都属于一个只包括自己的集合，并以自己为代表元素，然后根据题目条件逐一合并集合。

用一个Rank[]数组来维护集合的秩，避免“大树”挂在“小树”上面，使得树更高。

源代码

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxN = 30005;

int par[maxN];
int Rank[maxN];

void initial(int n) {
	for (int i = 0; i < n; i++) {
		par[i] = i;
		Rank[i] = 1;
	}
}

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

bool unit(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)//同一集合
		return false;
	if (Rank[x] > Rank[y])
		swap(x, y);//避免大的挂在小的名下
	par[x] = y;
	Rank[x] += Rank[y];
	Rank[y] = Rank[x];
	return true;
}

int main() {
	int n, m;
	while (scanf_s("%d%d", &n, &m) != EOF) {
		if (n == 0 && m == 0)
			break;
		initial(n);
		for (int i = 0; i < m; i++) {
			int num;
			scanf_s("%d", &num);
			int ori;
			scanf_s("%d", &ori);
			for (int j = 1; j < num; j++) {
				int a;
				scanf_s("%d", &a);
				unit(ori, a);
			}
		}
		int res = Rank[find(0)];
		printf("%d\n", res);
	}

	return 0;
}