POJ - 1611 The Suspects （kuangbin - 并查集）

题目描述(已转换成中文)

  新型冠状病毒肺炎（Corona Virus Disease 2019，COVID-19），简称“新冠肺炎”，是指2019新型冠状病毒感染导致的肺炎。
如果一个感染者走入一个群体，那么这个群体需要被隔离！
小A同学被确诊为新冠感染，并且没有戴口罩！！！！！！
  危！！！
  时间紧迫！！！！
  需要尽快找到所有和小A同学直接或者间接接触过的同学，将他们隔离，防止更大范围的扩散。
  众所周知，学生的交际可能是分小团体的，一位学生可能同时参与多个小团体内。
  请你编写程序解决！戴口罩！！

输入格式

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

输出格式

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

输入输出样例

输入

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

输出

4
1
1

题目链接

分析：

  这道题属于基本的并查集问题，目的是找出与元素0属于同个集合的元素有多少个，首先在每组测试开始前，要先对fu数组初始化为本身，接着读入每个小团体的元素，对团体里的所有元素都与团体的第一个元素进行合并，通过find函数进行路径压缩及元素根节点的寻找，如果不是属于同个集合，则把两个元素所在的集合合并在一起，最后用一个for循环，计算所有元素的父节点与元素0的父节点相同的元素个数。

这道题需要注意的地方：

  因为在每次判断x和y是否属于同个集合的时候，等价于判断x和y的根节点是否相同，在判断的过程中调用了find函数，find函数在寻找某元素根节点的过程中，会进行路径压缩，即元素i的根节点就是fu[i]。
在对两个元素x和y进行合并的时候，直接fu[fu[y]] = fu[x]即可，这样就实现了x集合的根节点成为y集合的根节点的根节点(听起来有点绕hhh)。

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int fu[30005], n, m;
int read(){
	int x, f = 1;
	char ch;
	while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
	x = ch - '0';
	while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
	return x * f;
}
int find(int x){
    if(x == fu[x]) 
		return x;
    return fu[x] = find(fu[x]);
}
int main(){
	int i, j, x, y, k, sum;
	while(1){
		sum = 1;
		n = read();
		m = read();
		if(m == 0){
			if(n == 0) break;
			else{
				printf("1n");
				continue;
			}
		}
		for(i = 0; i < n; i++) fu[i] = i;
		for(i = 1; i <= m; i++){
			k = read();
			x = read();
			for(j = 1; j < k; j++){
				y = read();
				if(find(x) != find(y)) fu[fu[y]] = fu[x];	
			}
		}
		for(i = 1; i < n; i++){
			if(find(0) == find(i)) sum++; 
		} 	
		printf("%dn", sum);
	}
	
	return 0;
}

最后

以上就是丰富枕头为你收集整理的POJ - 1611 The Suspects （kuangbin - 并查集）的全部内容，希望文章能够帮你解决POJ - 1611 The Suspects （kuangbin - 并查集）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。