六度空间

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

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

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;
}
目录
相关文章
|
6月前
|
机器学习/深度学习 算法 搜索推荐
【解密算法:时间与空间的博弈】(中)
【解密算法:时间与空间的博弈】
|
6月前
|
存储 算法
【解密算法:时间与空间的博弈】(上)
【解密算法:时间与空间的博弈】
|
传感器 数据采集 数据可视化
物理空间的三维重建
物理空间的三维重建
|
2月前
|
安全 UED
再次上演“空间魔法”,方太重新定义水槽洗碗机的能力边界
9月25日,方太在北京品牌超级体验店发布了全新一代水槽洗碗机Y系列,引发广泛关注。这款产品集水槽、洗碗机、果蔬净化机于一体,解决了传统洗碗机安装复杂、空间占用大等问题,尤其适合中国家庭厨房。自2015年推出首代水槽洗碗机以来,方太通过创新设计,如双层可翻转水流清洗系统和自动顶门透气干燥系统,大幅提升用户体验。此次Y系列不仅解决了洗锅难题,还增加了多功能料理台功能,进一步优化了厨房空间利用。方太凭借持续的技术创新和对中国家庭需求的深刻理解,成功引领了洗碗机市场的变革。
|
3月前
|
安全
【2023高教社杯】D题 圈养湖羊的空间利用率 问题分析、数学模型及MATLAB代码
本文介绍了2023年高教社杯数学建模竞赛D题的圈养湖羊空间利用率问题,包括问题分析、数学模型建立和MATLAB代码实现,旨在优化养殖场的生产计划和空间利用效率。
162 6
【2023高教社杯】D题 圈养湖羊的空间利用率 问题分析、数学模型及MATLAB代码
|
机器学习/深度学习 决策智能
矩阵分析 (二) 内积空间
矩阵分析 (二) 内积空间
170 0
|
6月前
|
存储 算法 编译器
【解密算法:时间与空间的博弈】(下)
【解密算法:时间与空间的博弈】
|
6月前
|
数据可视化 Python
金融数学方法:有限差分法
金融数学方法:有限差分法
175 0
|
机器学习/深度学习 算法 量子技术
希尔伯特空间:概念、原理与发展趋势
希尔伯特空间:概念、原理与发展趋势
496 0
金刚区计算个数效果实现
金刚区计算个数效果实现
72 0