POJ1611-The Suspects（并查集入门内附详解）

74 阅读 0 评论 49 点赞

我是靠谱客的博主正直小刺猬，这篇文章主要介绍POJ1611-The Suspects（并查集入门内附详解），现在分享给大家，希望可以做个参考。

题目链接：传送门
分析：该题为并查集入门，关于并查集入门可以看一下并查集详解（简单图文解说），看完基本就知道并查集的基本函数怎么写，这里还有另一道也是并查集入门的题目，可以用来练练手HDU1232畅通工程
分析：基本的并查集函数，稍微要处理一下的地方就是将suspect那一组的最顶端改为0，这样在清点人数的时候好找一点。
AC代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
using namespace std;
const int max_n=30005;
int n,m,a,b;
int pre[max_n];		//记录某点的上一个节点
void begin(){	//初始化处理
	for(int i=0;i<n;i++)
		pre[i]=i;
}
int find(int z){	//查找一组人群中最顶端的人
	int r=z;
	while(pre[r]!=r)
	r=pre[r];
	return r;
}
void unit(int x,int y){		//将x和y加到一组中
	int fx,fy;
	fx=find(x);
	fy=find(y);
	if(fx!=fy){
	pre[fx]=fy;
	}
}
void solve(){	// 处理将suspect那组的最顶端改为0（即为感染人）
	int r=find(0);
	pre[r]=0;
	pre[0]=0;
}
int main(){
	while(cin>>n>>m){
		if(n==0&&m==0)	break;
		if(m==0){
			cout<<"1"<<endl;
			continue;
		}
		begin();
		int t;
		for(int i=0;i<m;i++){
			cin>>t;
			cin>>a;
			for(int j=0;j<t-1;j++){
				cin>>b;
				unit(a,b);
			}
		}
		int ans=0;
		solve();
		for(int i=0;i<n;i++)
		if(find(i)==0)	ans++;		//如果是0那组人就
		cout<<ans<<endl;
	}
}