poj1611 the suspects（并查集）

78 阅读 0 评论 52 点赞

我是靠谱客的博主忧伤老师，这篇文章主要介绍poj1611 the suspects（并查集），现在分享给大家，希望可以做个参考。

并查集裸题。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>
#define N 30005 
int fa[N],n,m;
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
//  freopen("a.in","r",stdin);
    while(1){
        int ans=1;
        scanf("%d%d",&n,&m);
        if(n==0&&m==0) break;
        for(int i=0;i<n;++i) fa[i]=i;
        while(m--){
            int k,a,b;
            scanf("%d%d",&k,&a);
            for(int i=1;i<k;++i){
                scanf("%d",&b);
                int xx=find(a),yy=find(b);
                if(xx!=yy) f[yy]=xx;
            }
        }
        for(int i=1;i<n;++i)
            if(find(i)==find(0)) ans++;
        printf("%dn",ans);
    }
    return 0;
}