http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=357#problem/C
这道题不难解,关键是理解清楚
#include<stdio.h>
#define N 50005
int n,f[N],c[N];
void init(){//初始化
    int i;
    for(i=0;i<n;i++){
        f[i]=i;
        c[i]=1;
    }
}
int find(int x){//查找
    if(x!=f[x])
        return f[x]=find(f[x]);
    return x;
}
void unio(int x,int y){//合并
    x=find(x);
    y=find(y);
    if(x==y)
        return ;
    else if(x<y){
        f[y]=x;
        c[x]+=c[y];
    }
    else{
        f[x]=y;
        c[y]+=c[x];
    }
}
int main(){
    int m,k,x,y;
    while(scanf("%d%d",&n,&m)&&(n||m)){
        if(m==0)//m为零的情况直接输出
            printf("%d\n",n);
        else{
            init();
            while(m–){
                scanf("%d%d",&k,&x);
                k–;//k为组中成员数
                while(k–){
                    scanf("%d",&y);
                    unio(x,y);
                    x=y;//准备换下一组x,y
                }
            }
            printf("%d\n",c[0]);//c[0]即所有的嫌疑人数
        }
    }
    return 0;
}
 

发表评论

电子邮件地址不会被公开。

Post Navigation