poj1611(并查集简单应用)

时间:2022-03-05 03:13:44

题目链接:http://poj.org/problem?id=1611

思路:

显然是一个并查集的题,很简单,只要将一个group中的学生并在一起,最后遍历1到n-1,看有多少学生的祖先与0的祖先相等即可。

代码如下:

 #include<cstdio>
using namespace std; int n,m,res,root[]; int getr(int k){
if(root[k]==k) return k;
else return root[k]=getr(root[k]);
} int main(){
while(~scanf("%d%d",&n,&m),n){
res=;
for(int i=;i<n;++i) root[i]=i;
while(m--){
int num,tmp1,tmp2;
scanf("%d",&num);
if(num>){
scanf("%d",&tmp1);
num--;
while(num--){
scanf("%d",&tmp2);
root[getr(tmp2)]=getr(tmp1);
}
}
}
int tmp=getr();
for(int i=;i<n;++i)
if(getr(i)==tmp)
++res;
printf("%d\n",res);
}
return ;
}