并查集poj1611The Suspects

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