并查集poj1611The Suspects

#include<iostream>
using namespace std;
const int MAX=30010;
int pre[MAX];
void init(int n){
	for(int i=0;i<n;i++)
	pre[i]=i;
}
int find(int x){
	if(pre[x]==x) return x;
	return pre[x]=find(pre[x]);
}
void unite(int x,int y){
	x=find(x);
	y=find(y);
	if(x==y) return;
	pre[x]=y;
}
bool same(int x,int y){
	return find(x)==find(y);
}
int n,m;
int main(){
	ios::sync_with_stdio(false);
	while(cin>>n>>m&&n){
		init(n);
		int t,tmp,k;
		while(m--){
			cin>>k;
		if(k==0) continue;		
			cin>>t;
			for(int i=1;i<k;i++){
				cin>>tmp;
				unite(tmp,t);
			}		
		}
		int ans=0;
		for(int i=0;i<n;i++){
			if(same(0,i)) ans++;
		}
	cout<<ans<<endl;	
	}
	return 0;
}

最后

以上就是合适灯泡为你收集整理的并查集poj1611The Suspects的全部内容，希望文章能够帮你解决并查集poj1611The Suspects所遇到的程序开发问题。

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