文档章节

Codevs 6个朋友

机智的帝江
 机智的帝江
发布于 2016/10/30 09:59
字数 797
阅读 2
收藏 0

点击就送屠龙宝刀

题目描述 Description

有这么一种说法:认识6个人,你就认识全世界的人。

Aiden现在有一张关系图,上面记载了N个人之间相互认识的情况。Aiden想知道,他能否只认识6个人就能间接认识这N个人呢?
输入描述 Input Description

第一行,两个数N,M,表示有N个人,M对认识关系。

接下来的M行,每行两个数ai,bi,表示ai与bi相互认识。

不保证认识关系不出现重复,保证ai≠bi。

N个人的编号为1…N。
输出描述 Output Description

若只认识6个人就能间接认识这N个人,则输出“^_^”。

若不行,则第一行输出“T_T”,第二行输出认识6个人最多能间接认识的人的个数。

输出不包括引号。
样例输入 Sample Input

6 7

1 2

1 3

2 4

3 5

4 6

5 6

3 2
样例输出 Sample Output

^_^
数据范围及提示 Data Size & Hint

对于30%的数据,保证0<n≤1000。

对于50%的数据,保证0<n≤5000。

对于100%的数据,保证0<n≤10000,m≤10*n。

这个题怎么说呢,槽点满满的。。首先肯定是用并查集来实现,这个肯定可以看出来。然后可以各种脑洞实现啦23333.刚开始我想的是添加一个use数组记录是否找到过然后停止的时候把这个数扔到一个vector里面排序然后取前6个(如果足够多的话)。然而莫名RE于是想到了另外一个脑洞方式
我们可以在用并查集寻找的时候记录满足条件的编号,然后利用集合合并的方式来计算前6(足够大的情况下)组的和,然后根据条件判断输出就可以了。
总的来说这题难度不大甚至可以说是代码能力练习题23333.

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;
int father[10010]={0};
int sum[10010]={0};

int find(int x)
{
    if (father[x]==x)
    return x;
    else
    {
      father[x]=find(father[x]);
      return father[x];
    }
}//并查集路径压缩find

void merge(int x,int y)
 {
      int f1=find(x);
      int f2=find(y);
      if (f1!=f2)
        {
           father[f1]=f2;
           sum[f2]+=sum[f1];//记录以这个集合为代表元素的集合的元素个数
        }
 }//并查集合并

int main()
     {
      int i,j,k,x,y,z,n,m;
      scanf("%d%d",&n,&m);
      for (i=1;i<=n;i++)
         {
      father[i]=i;
      sum[i]=1;
         }//并查集初始化,加元素个数的数组初始化
      for (i=1;i<=m;i++)
      {
      scanf("%d%d",&x,&y);
      merge(x,y);
        }
        int ans=0;
        int bh[10010]={0};//记录满足条件的集合的编号
        k=1;
      for (i=1;i<=n;i++)
       {
        if (find(i)==i)
        {
         ans++;
         bh[k]=i;
         k++;
         }
       }//找有几个集合k为保存集合数的下标,ans为集合数
      for (i=1;i<=k;i++)
       {
        bh[i]=sum[bh[i]];
       }//把集合数变成集合里元素数
     int ans1=0;
      sort(bh+1,bh+k+1);
      for (i=k;i>=k-5;i--)
       ans1+=bh[i];//前6大的集合的元素总数,不满足认识6 人就认识世界的时候输出
      if (ans<=6)
       printf("^_^");
      else
       {
        printf("T_T");
        printf("\n%d",ans1);
       }
     return 0;
}

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/49200481

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
splay的各种操作与简易讲解

基本操作 插入 和二叉查找树一样,但是插入完成后要splay一下(即伸展),伸展操作下面有 伸展 查找前驱或后驱 例题:codevs1285/洛谷P2286/bzoj1208 宠物收养所 删除和合并 先把要删除的点s...

litble
2017/07/07
0
0
codevs 5971 打击犯罪

题目描述 Description 某个地区有n(n<=1000)个犯罪团伙,当地警方按照他们的危险程度由高到低给他们编号为1-n,他们有些团伙之间有直接联系,但是任意两个团伙都可以通过直接或间接的方式联系...

zoom1109
06/19
0
0
用tarjan求最近公共祖先

原文地址https://www.cnblogs.com/JVxie/p/4854719.html LCA 最近公共祖先 Tarjan(离线)算法的基本思路及其算法实现 小广告:METO CODE 安溪一中信息学在线评测系统(OJ)       //由于这...

weixin_39872717
2017/11/09
0
0
[codevs3123]大整数乘法(快速傅立叶变换FFT)

【题意】 给出两个整数a和b,输出a*b的值 【输入】 输入两行 第一行输入a 第二行输入b 【输出】 输出一行 输出a*b 【样例输入】 2 3 【样例输出】 6 【提示】 1<=a<=10^100000,1<=b<=10^100...

CABI_ZGX
2017/12/03
0
0
Duan2baka的各种LCA模板!

(这篇文章是模板向…了解具体思想还是看网上其他详细讲解吧QAQ) LCA,即最近公共祖先,是在有根树中两个点最近的公共祖先,在树上问题中非常有用QAQ 常用LCA求法: 一、树链剖分LCA 树链剖分...

WADuan2
2017/10/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring使用ThreadPoolTaskExecutor自定义线程池及实现异步调用

多线程一直是工作或面试过程中的高频知识点,今天给大家分享一下使用 ThreadPoolTaskExecutor 来自定义线程池和实现异步调用多线程。 一、ThreadPoolTaskExecutor 本文采用 Executors 的工厂...

CREATE_17
今天
5
0
CSS盒子模型

CSS盒子模型 组成: content --> padding --> border --> margin 像现实生活中的快递: 物品 --> 填充物 --> 包装盒 --> 盒子与盒子之间的间距 content :width、height组成的 内容区域 padd......

studywin
今天
7
0
修复Win10下开始菜单、设置等系统软件无法打开的问题

因为各种各样的原因导致系统文件丢失、损坏、被修改,而造成win10的开始菜单、设置等系统软件无法打开的情况,可以尝试如下方法解决 此方法只在部分情况下有效,但值得一试 用Windows键+R打开...

locbytes
昨天
8
0
jquery 添加和删除节点

本文转载于:专业的前端网站➺jquery 添加和删除节点 // 增加一个三和一节点function addPanel() { // var newPanel = $('.my-panel').clone(true) var newPanel = $(".triple-panel-con......

前端老手
昨天
8
0
一、Django基础

一、web框架分类和wsgiref模块使用介绍 web框架的本质 socket服务端 与 浏览器的通信 socket服务端功能划分: 负责与浏览器收发消息(socket通信) --> wsgiref/uWsgi/gunicorn... 根据用户访问...

ZeroBit
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部