题目链接: http://poj.org/problem?id=1611
思路:
显然是一个并查集的题, 很简单, 只要将一个 group 中的学生并在一起, 最后遍历 1 到 n-1, 看有多少学生的祖先与 0 的祖先相等即可.
代码如下:
- #include<cstdio>
- using namespace std;
- int n,m,res,root[30005];
- 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=1;
- for(int i=0;i<n;++i) root[i]=i;
- while(m--){
- int num,tmp1,tmp2;
- scanf("%d",&num);
- if(num>0){
- scanf("%d",&tmp1);
- num--;
- while(num--){
- scanf("%d",&tmp2);
- root[getr(tmp2)]=getr(tmp1);
- }
- }
- }
- int tmp=getr(0);
- for(int i=1;i<n;++i)
- if(getr(i)==tmp)
- ++res;
- printf("%d\n",res);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2971221.html