POJ - 1611 The Suspects（并查集）

50 阅读 0 评论 33 点赞

我是靠谱客的博主坦率机器猫，最近开发中收集的这篇文章主要介绍POJ - 1611 The Suspects（并查集），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

2003年4月16日，世界卫生组织根据包括中国内地和香港地区，加拿大、美国在内的11个国家和地区的13个实验室通力合作研究的结果，宣布重症急性呼吸综合征的病因是一种新型的冠状病毒，称为SARS冠状病毒。
很不幸，小明同学昨天晚上被确诊以经感染非典病毒，为此，校医院需要对他隔离治疗并隔离观察与他直接或间接接触者。
可以认为，同一个社团内如果有人感染病毒或可能感染病毒，那么这个社团内所有人都被认为是可能已经感染了病毒，由于时间紧迫，需要尽快找到所有可能携带病毒的同学并隔离，以防止更大范围的病毒扩散，院长请你帮忙编写程序计算需要隔离多少人

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

代码如下：

#include<iostream>
#include<vector>

const int maxn = 3e4 + 5;
int a[maxn];
int n, m;

void init(int n){
	for(int i = 0; i < n; i ++){
		a[i] = i;
	}
}

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

void unionn(int x, int y){
	int a1 = find(x);
	int a2 = find(y);
	a[a1] = a2;
}


int main(){
	std::ios::sync_with_stdio(false);
	std::cout.tie(NULL);
	
	
	while(std::cin >> n >> m && (m + n)){
		
		if(m == 0){
			std::cout<< 1 << std::endl;
			continue;
		}
		
		init(n);
		std::vector<int> v;
		for(int i = 0; i < m; i ++){
			int k;
			std::cin >> k;
			
			v.clear();
			for(int j = 0; j < k; j ++){
				int x;
				std::cin >> x;
				v.push_back(x);
			}
	
			for(int i = 1; i < v.size(); i ++){
				unionn(v[i - 1], v[i]);
			}
		
		}
		
			int cnt = 0;
			int t = find(0);
			for(int i = 0; i < n; i ++){
				if(find(i) == t){
					cnt ++;
				}
			}
			std::cout << cnt << std::endl;
	}
	return 0;
}