L3-008 喊山 (30 分)(bfs)

简介: L3-008 喊山 (30 分)(bfs)

喊山,是人双手围在嘴边成喇叭状,对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递,回荡于深谷之间,传送到人们耳中,发出约定俗成的“讯号”,达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”,慢慢地人们在生活实践中发现了它的实用价值,便把它作为一种交流工具世代传袭使用。(图文摘自:http://news.xrxxw.com/newsshow-8018.html

d8d5c4ed3ca04bf271dad905a62169b0.jpg


一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头,本题请你找出这个信号最远能传达到的地方。


输入格式:

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


输出格式:

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


输入样例:

1. 7 5 4
2. 1 2
3. 2 3
4. 3 1
5. 4 5
6. 5 6
7. 1 4 5 7


输出样例:

1. 2
2. 6
3. 4
4. 0


思路:一层一层遍历,途中记录一下每个相连的编号在那一层

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int level[N],vis[N];
vector<int>v[N];
int n,m,k;
int bfs(int u)
{
    memset(vis,0,sizeof vis);
    memset(level,0,sizeof level);
    queue<int>q;
    q.push(u);
    while(!q.empty())
    {
        int x=q.front();
        vis[x]=1;
        q.pop();
        for(int i=0;i<v[x].size();i++)
        {
            if(!level[v[x][i]]&&!vis[v[x][i]])
            {
                level[v[x][i]]=level[x]+1;
                vis[v[x][i]]=1;
                q.push(v[x][i]);
            }
        }
    }
    int maxx=0;
    for(int i=1;i<=n;i++)
        if(maxx<level[i]) maxx=level[i];//保存最大层数
    for(int i=1;i<=n;i++)
        if(maxx&&maxx==level[i]) return i;//返回最大层数的最小编号,无相连的跳过
    return 0;
}
int main()
{
    cin>>n>>m>>k;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    int x;
    while(k--)
    {
        cin>>x;
        cout<<bfs(x)<<endl;
    }
    return 0;
}
目录
相关文章
|
机器学习/深度学习 存储 算法
【DFS经典例题】2n皇后问题
【DFS经典例题】2n皇后问题
76 0
|
机器学习/深度学习 算法 测试技术
C++算法:01BFS最短距离的原理和实现
C++算法:01BFS最短距离的原理和实现
|
存储 索引
树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
树与图中的dfs和bfs—— AcWing 846. 树的重心 AcWing 847. 图中点的层次
78 0
|
算法
BFS——二分图判断
BFS——二分图判断
120 0
BFS——二分图判断
|
存储
L2-031 深入虎穴 (25 分)(bfs)
L2-031 深入虎穴 (25 分)(bfs)
203 0
L2-031 深入虎穴 (25 分)(bfs)
|
存储 算法 C语言
6-1 最小生成树(普里姆算法) (10分)
6-1 最小生成树(普里姆算法) (10分)
6-1 最小生成树(普里姆算法) (10分)
|
算法 Java Python
【算法题解】 Day6 BFS | DFS
今天的算法是 「BFS | DFS」 相关,“算法题解系列文章旨在精选重点与易错的算法题,总结常见的算法思路与可能出现的错误,以实战习题的形式理解算法,使用算法。”
103 0
【CCCC】L3-008 喊山 (30分),BFS搜索最长路,水题
【CCCC】L3-008 喊山 (30分),BFS搜索最长路,水题
107 0
L2-026 小字辈 (25 分)(bfs)
L2-026 小字辈 (25 分)(bfs)
127 0
|
算法 C++ Python
BFS逛街算法模板-附LeetCode习题-433. 最小基因变化-广度优先搜索
BFS逛街算法模板-附LeetCode习题-433. 最小基因变化-广度优先搜索