The Suspects 【并查集】超详细题解

阳光穿透心脏的1/2处 2021-08-29 18:18 301阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.题意
         *  3.思路
         *  4.代码

### 1.题目 ###

严重急性呼吸系统综合症( SARS), 一种原因不明的非典型性肺炎,从2003年3月中旬开始被认为是全球威胁。为了减少传播给别人的机会, 最好的策略是隔离可能的患者。  
在Not-Spreading-Your-Sickness大学( NSYSU), 有许多学生团体。同一组的学生经常彼此相通,一个学生可以同时加入几个小组。为了防止非典的传播,NSYSU收集了所有学生团体的成员名单。他们的标准操作程序(SOP)如下：  
一旦一组中有一个可能的患者, 组内的所有成员就都是可能的患者。  
然而,他们发现当一个学生被确认为可能的患者后不容易识别所有可能的患者。你的工作是编写一个程序, 发现所有可能的患者。

Input  
输入文件包含多组数据。  
对于每组测试数据：  
第一行为两个整数n和m, 其中n是学生的数量, m是团体的数量。0 < n <= 30000，0 <= m <= 500。  
每个学生编号是一个0到n-1之间的整数，一开始只有0号学生被视为可能的患者。  
紧随其后的是团体的成员列表，每组一行。  
每一行有一个整数k，代表成员数量。之后,有k个整数代表这个群体的学生。一行中的所有整数由至少一个空格隔开。  
n = m = 0表示输入结束，不需要处理。  
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  
Sample Output  
4  
1  
1

### 2.题意 ###

一开始只有0号学生被视为可能的患者，与0号患者直接或间接接触的人都视为可能患者，求出所有可能的患者。

### 3.思路 ###

经典的并查集题目。建立一个并查集，将所有直接或间接关联的学生都放在一个集合中，统计与0号元素在一个集合中元素的个数。遍历所有学生，当某个学生的根节点与0号学生的根节点相同时，即视为在同一集合。需要注意的是当团队数为0时表示每个人都是独立的个体，因此只有0号学生为可能的患者，输出1。  
链接: [并查集模板][Link 1].  
链接: [并查集学习][Link 2].

### 4.代码 ###

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=3e4+10;
    int Fa[maxn], Rank[maxn],a[maxn];
    void init(int n)
    { 
    	for (int i = 0; i < n; i++)
    	{ 
    		Fa[i] = i;
    		Rank[i] = 1;
    	}
    }
    int find(int x)
    { 
    	return x == Fa[x] ? x : (Fa[x] = find(Fa[x]));//路径压缩
    }
    void merge(int i, int j)
    { 
    	int x = find(i), y = find(j);
    	if (Rank[x] <= Rank[y])
    	{ 
    		Fa[x] = y;
    	}
    	else
    	{ 
    		Fa[y] = x;
    	}
    	if (Rank[x] == Rank[y] && x!=y)
    	{ 
    		Rank[y]++;
    	}
    }
    int main()
    { 
    	int n, m;
    	while (cin >> n >> m)
    	{ 
    		if (n == 0&&m==0) break;
    		init(n);
    		if (m == 0)//团队数为0表示每个人都是独立的个体，因此只有0号学生为可能的患者
    		{ 
    			cout << "1" << endl;
    			continue;
    		}
    		while(m--)
    		{ 
    			int k;
    			cin >> k;
    			cin >> a[0];
    			for (int j = 1; j < k; j++)
    			{ 
    				cin >> a[j];
    				merge(a[0], a[j]);
    			}
    		}
    		int cnt = 0;
    		for (int i = 0; i < n; i++)
    		{ 
    			if (find(i) == find(0))
    			{ 
    				cnt++;
    			}
    		}
    		cout << cnt << endl;
    	}
    	return 0;
    }

[Link 1]: https://blog.csdn.net/weixin_45629285/article/details/106104364/
[Link 2]: https://zhuanlan.zhihu.com/p/93647900/