六度空间

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

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;
}