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