简单并查集标题:hdu 1213"How Many Table"


hdu 1213"How Many Tables"
ある人はいっしょに食事をして、一部の人は互いに知り合います.知っている人は一緒に座りたいし、知らない人と座りたくない.例えばAがBを知っていて、BがCを知っていると、A、B、Dはテーブルの上に座っています.
分析:テーブルは集合で、友人関係を統合し、数を統計すればいいです.次は、コードを調べてセットを調べる操作です.
#include 
using namespace std;
const int maxn=1050;
int s[maxn];
void init_set(){//    
	for(int i=1; i<=maxn; i++)
		s[i]=i; 
}
int find_set(int x){//   
	return x ==s[x]? x:find_set(s[x]);
	//     ,     , ,         
}
int union_set(int x,int y){//   
	x =find_set(x);
	y =find_set(y);
	if(x!= y) s[x] =s[y];
}
int main(){
	int t,n,m,x,y;//m:     ,n:     
	cin>>t;
	while(t--){
		cin>>n>>m;
		init_set();
		for(int i=1; i<=m;i++){
		  cin>>x>>y;
		  union_set(x,y); 
		}
		int ans=0;
		for(int i=1;i<=n;i++)
			if(s[i] ==1)
				ans++;
		cout<<ans<<endl; 
	}
	return 0;
}