L3-008. 喊山

一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头，本题请你找出这个信号最远能传达到的地方。【何为最远？大致就是BFS的遍历层次吧，可以说是了。】

输入格式：

输入第一行给出3个正整数n、m和k，其中n（<=10000）是总的山头数（于是假设每个山头从1到n编号）。接下来的m行，每行给出2个不超过n的正整数，数字间用空格分开，分别代表可以听到彼此【这里说明是双向边！】的两个山头的编号。这里保证每一对山头只被输入一次，不会有重复的关系输入。最后一行给出k（<=10）个不超过n的正整数，数字间用空格分开，代表需要查询的山头的编号。

输出格式：

依次对于输入中的每个被查询的山头，在一行中输出其发出的呼喊能够连锁传达到的最远的那个山头。注意：被输出的首先必须是被查询的个山头能连锁传到的。若这样的山头不只一个，则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头，则输出0。

输入样例：

7 5 4

1 2

2 3

3 1

4 5

5 6

1 4 5 7【7是一个孤立的点，输出其自身！】

输出样例：

AC题解，有详细注释呦：

虽然是level-3的题目，但其实也怪简单！加油！相信自己！

 #include<iostream>

 #include<stdio.h>

 #include<string.h>

 #include<math.h>

 #include<algorithm>

 #include<queue>

 #include<set>

 #include<vector>

 #include<string>

 #include<stack>

 #define  inf 0x3f3f3f3f

 #define  dinf 0x7fffffff*1.0

 using namespace std;   //L3-008. 喊山

 #define N 10008

 #define ll long long

 struct node{

     int x,step;

     node(int x=,int step=):x(x),step(step){}//构造函数

 };

 vector<int>G[N];//构建邻接矩阵

 int vis[N];

 int bfs(int st){//st是start的缩写，表示开始搜索的点

     memset(vis,,sizeof(vis));//标记数组，以免重复访问

     queue<node>Q;

     Q.push(node(st,));

     vis[st]=;

     int maxdeep=;//对st来说，可以达到的最大搜索深度

     int ans=inf;

     node now;

     while(Q.size()){//每次从队首获得并删除一个点，然后遍历完他的子节点——没标记过的就再次加入队列中

         now=Q.front();

         Q.pop();

   //      printf(" *%d/%d* ",now.x,now.step);

         if(now.step>maxdeep){

             maxdeep=now.step;

             ans=now.x;

         }else if(now.step==maxdeep){

             ans=min(ans,now.x);

         }

         for(int i=;i<(int)G[now.x].size();i++){

             int v=G[now.x][i];//取出now.x在邻接矩阵中的一个子节点V

             if(!vis[v]){

                 vis[v]=;

                 Q.push(node(v,now.step+));

             }

         }

     }

     return (ans==st?:ans);//考虑0的特例

 }

 int main(){

     int n,m,k;

     scanf("%d%d%d",&n,&m,&k);

     int u,v;

     for(int i=;i<=n;i++){

         G[i].clear();

     }

     for(int i=;i<=m;i++){

         scanf("%d%d",&u,&v);

         G[u].push_back(v);

         G[v].push_back(u);

     }

     for(int i=;i<=k;i++){

         scanf("%d",&u);

         printf("%d\n",bfs(u));

     }

     return ;

 }

喊山

【邻接矩阵+基础BFS】PAT-L3-008. 喊山

L3-008. 喊山