六度空间

简介: 题目描述 在数学领域的有一个神秘迷人的猜想叫做六度空间理论: 你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个中间人你就能够认识任何一个陌生人.

题目描述
在数学领域的有一个神秘迷人的猜想叫做六度空间理论: 你和任何一个陌生人之间所间隔的人不会超过六个,也就是说,最多通过五个中间人你就能够认识任何一个陌生人.

PP是北京化工大学的一只普通单身汪,他每天总是早早的起床,然后屁颠屁颠的背上自己的小书包高高兴兴的去上课.PP觉得这样的生活很幸福. 然而周围总有一些可恶的邪恶汪在PP周围秀恩爱,喂PP吃狗粮.这打击到了PP,PP很生气,决心也找一个同伴.

有一天PP在去食堂的路上,遇见了一只特别美丽的汪汪RR.PP深深地被它所吸引,但PP不认识它,又不好意思向它主动打招呼.这时PP想到了六度空间理论.想通过自己认识的汪间接认识RR.

现在有编号从1到n的n只汪,其中PP的编号为1,RR的编号为n.(2<=n<100000)

有m条认识关系,关系的表示形式为a b.表示:编号为a的汪认识编号为b的汪,与此同时编号为b的汪认识编号为a的汪(双向认识).(0<=m<100000,1<=a,b<=n且a!=b)

问PP能否最多中间通过5只汪间接认识美丽的RR,如果能输出”PP will be happy!”(没有引号),否则输出”PP will die!”(没有引号).

输入
输入只包含一组数据.

第一行一个整数n表示有n只汪

第二行有一个整数m表示有m种关系

接下来有m行每行有两个数字a b(中间用空格隔开).表示a认识b,同时b认识a

(数据建议用scanf读入)

输出
如果PP可以最多通过中间的五个人认识RR,就输出:”PP will be happy!”,

否则输出: “PP will die!”.(输出结束之后记得换行)

样例输入
6
5
1 2
1 3
1 4
2 3
5 6
样例输出
PP will die!

考察的是图的vector邻接表和搜索。

#include<bits/stdc++.h>
using namespace std;

vector<int>p[100005];
bool vis[100005];

struct Node{
    int place;
    int Step;
};

void BFS(int start,int en){
    queue<Node>Q;
    Node now,next;
    now.place=start;
    now.Step=0;
    Q.push(now);
    vis[start]=1;
    while(!Q.empty()){
        now=Q.front();
        Q.pop();
        if(now.place==en&&now.Step<=6){
            printf("PP will be happy!");
            return;
        }
        for(int i=0;i<p[now.place].size();i++){
            if(!vis[p[now.place][i]]){
                next.place=p[now.place][i];
                vis[next.place]=1;
                next.Step=now.Step+1;
                Q.push(next);
            }
        }
    }
    printf("PP will die!");
}

int main(){
    int n;
    cin>>n;
    int m;
    cin>>m;
    int a,b;
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        p[a].push_back(b);
        p[b].push_back(a);
    }
    BFS(1,n);
    return 0;
}
目录
相关文章
|
机器学习/深度学习 决策智能
矩阵分析 (二) 内积空间
矩阵分析 (二) 内积空间
174 0
|
机器学习/深度学习 算法 量子技术
希尔伯特空间:概念、原理与发展趋势
希尔伯特空间:概念、原理与发展趋势
501 0
金刚区计算个数效果实现
金刚区计算个数效果实现
78 0
|
传感器 物联网 计算机视觉
智慧办公空间的“出圈”,如何做到的?
阿里云·云上办公解决方案(以下简称“云上办公解决方案”)以办公智能化、数字化、简单化、高效化为目标,采用多对多、云边端一体化架构,使用低功耗蓝牙传输技术,在省时省事省钱的同时提供高可用、高并发、高效稳定的云上办公整体物联网解决方案。
|
新零售 数据采集 算法
网约车之外,滴滴有哪些空间值得重新想象?
滴滴的价值在哪?国内市场之外,还有更远的征程以及更大的想象空间——程维、柳青给出的答案是,“全球最大汽车运营商”和“智能交通技术的引领者”。
174 0
网约车之外,滴滴有哪些空间值得重新想象?
|
存储 机器学习/深度学习 移动开发
冰与火之歌:「时间」与「空间」复杂度 | 算法必看系列三十六
对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间; 反之,求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。
冰与火之歌:「时间」与「空间」复杂度 | 算法必看系列三十六
|
存储 缓存 算法
史上最详细Java内存区域讲解
常见面试题 基本问题 介绍下 Java 内存区域(运行时数据区) Java 对象的创建过程(五步,建议能默写出来并且要知道每一步虚拟机做了什么) 对象的访问定位的两种方式(句柄和直接指针两种方式) 拓展问题 String类和常量池 8种基本类型的包装类和常量池 一、概述 对于 Java 程序员来说,在虚拟机自动内存管理机制下,不再需要像C/C++程序开发程序员这样为内一个 new 操作去写对应的 delete/free 操作,不容易出现内存泄漏和内存溢出问题。
1439 0
浙江:孵化器、众创空间可设集体户口
4月28日上午,浙江省公安厅正式发布《浙江省常住户口登记管理规定》及10条便民举措,规定将于5月1日正式实施。
|
机器学习/深度学习 人工智能 机器人
《可以量化的经济学》之力量F与分配理论
经济学之力量F与分配理论 内容提要:本节通过广义动量定理和系统思考来论述收入的10种方式,指出成果的产生有贡献就会获得收入。 创新要点:使用广义动量定理和系统思考分析了收入的来源,指出了收入来源的多种方式,而不是仅仅局限于劳动。
1026 0