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("1\n"); 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("%d\n", sum); } return 0; }