2017-01-16 新生训练题F题菜鸟微见解

题意给你n个人,编号从0到n-1,再给你m个组,接下来的m行分别输入该组有多少人,且分别为编号为多少.0号是病毒感染者,与0号直接或间接在一起的都有可能感染该病毒,要求你输出可能感染病毒的人数(包括0号).

思路:并查集思想,因为0号是感染源,所以我们再输入组数人员编号时,统一把大的号数往小的上面并,则每组人员都链接起来了,则我们直接遍历一下pre数组中有多少个0就可以了.(因为最小为0号,跟他有关系的pre中最终都是0号)

代码如下:

#include<cstdio>
const int maxn=30007;
int n,m,pre[maxn];
int Find(int x){
    if(x==pre[x])   return x;
    return Find(pre[x]);
}

void Union(int x,int y){//与通常的有点不一样的写法.
    int m=Find(x);
    int n=Find(y);
    if(n<m){
        pre[m]=n;
    }
    if(n>m){
        pre[n]=m;
    }
}

void ini()
{
    for(int i=0;i<n;i++){
        pre[i]=i;
    }
}

int main()
{   int k,a,b;
    while(scanf("%d %d",&n,&m)!=EOF && n!=0 || m!=0){
        ini();
        for(int i=0;i<m;i++){
            scanf("%d",&k);
            scanf("%d",&a);
            for(int j=1;j<k;j++){
                scanf("%d",&b);
                Union(a,b);
            }
        }
        int ans=0;
        for(int i=0;i<n;i++){
            if(!Find(i))
                ans++;
        }
        printf("%d\n",ans);
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 土生水长阅读 310评论 0 0
  • 接上 不惑之年的老陈回老家看父母,通过好友得知景德镇在建设工业园区,政府扶持力度很大,反复思考研讨后...
    韦姐姐私房茶阅读 286评论 4 1
  • 1. 我们相识在一个培训课堂上,后来加微信认识,由同学发展成恋人关系。 2.他带着一副眼镜,看着很文绉绉的样子。白...
    你不宣我我宣你阅读 203评论 0 0
  • 好久没有动笔了。可能是很长时间自己都不敢去直面内心的困惑,也就更不敢将这种恐惧付诸于纸上了。 有人说的好,人们大多...
    simijoin阅读 231评论 0 0