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

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

#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;
	}
}

最后

以上就是正直小刺猬为你收集整理的POJ1611-The Suspects（并查集入门内附详解）的全部内容，希望文章能够帮你解决POJ1611-The Suspects（并查集入门内附详解）所遇到的程序开发问题。

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