传递消息1

试题描述

 我们班共有n名同学，编号1至n。其中，有m对无话不说的好朋友。作为一对无话不说的好朋友，只要其中一个人知道了什么小秘密，就会立即告知另一个人。

    现在，1号同学知道了一个小秘密，请问班上哪些同学会知道这个小秘密？此外，知道小秘密的同学分别都是通过几次消息传递知道这个秘密的？

输入

第一行包含两个正整数n、m，分别表示同学数量和朋友对数。
随后m行，每行包含两个正整数，表示一对朋友。

输出

请输出n行，每行一个整数。对于第i行的整数，若i号同学知道这个秘密，请输出它是通过几次消息传递知道这个秘密的；若i号同学不知道这个秘密，请输出-1。

输入示例

6 5
1 2
2 3
3 1
3 4
4 5

输出示例

0
1
1
2
3
-1

其他说明

对于30%的数据，n<=100, m<=200；
    对于60%的数据，n<=1000, m<=2000；
　　对于100%的数据，n<=100000, m<=200000。

思路：

1.初始化：①dis ②q

2.while(队列非空){

    ①s++=1（将队尾元素退出一个）

    ②找相邻点

        若dis==-1 {(1)加入队列 (2)修改小s}

#include <iostream>

using namespace std;
struct Edge   //结构体 
{
    int x,y,next;
}map[401010];  //由于是无向图，所以范围要 ×2 

int head[101010];

void add_edge(int i,int x,int y)
{
    map[i].x=x;
    map[i].y=y;
    map[i].next=head[x];
    head[x]=i;
}

int dis[201010],q[201010],st,ed;   //dis是每个顶点的距离，也是最后答案;q是队列;st=start,ed=end 

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) head[i]=-1;   //全部初始化为-1，方便后面找终点 
    for(int i=0;i<m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add_edge(2*i,x,y);   //如果只写一个，建的是有向图
        add_edge(2*i+1,y,x);   //为了不让后面的覆盖前面的，i的位置不能相同 
    }
    //以下是初始化-------------------------- 
    for(int i=1;i<=n;i++) dis[i]=-1;
    dis[1]=0;
    st=ed=0;  //队列清空（初始化）
    q[ed++]=1;
    //以上是初始化--------------------------
    while(st<ed)  //队列非空
    {
        int now=q[st++];  //取出一个元素
        for(int j=head[now];j!=-1;j=map[j].next)
        {
            if(dis[map[j].y]==-1)   //这个人还不知道消息
            {
                q[ed++]=map[j].y;
                dis[map[j].y]=dis[now]+1;
            } 
        } 
    }
   for(int i=1;i<=n;i++) printf("%d
",dis[i]);
    //system("pause");
    return 0;
}