简单并查集标题:hdu 1213"How Many Table"
hdu 1213"How Many Tables"
ある人はいっしょに食事をして、一部の人は互いに知り合います.知っている人は一緒に座りたいし、知らない人と座りたくない.例えばAがBを知っていて、BがCを知っていると、A、B、Dはテーブルの上に座っています.
分析:テーブルは集合で、友人関係を統合し、数を統計すればいいです.次は、コードを調べてセットを調べる操作です.
ある人はいっしょに食事をして、一部の人は互いに知り合います.知っている人は一緒に座りたいし、知らない人と座りたくない.例えば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;
}