【BFS问题】喊山  题解
2023-04-09
369
喊山,是人双手围在嘴边成喇叭状,对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递,回荡于深谷之间,传送到人们耳中,发出约定俗成的“讯号”,达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”,慢慢地人们在生活实践中发现了它的实用价值,便把它作为一种交流工具世代传袭使用。 一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头,本题请你找出这个信号最远能传达到的地方。
本文为本站原创,未经允许请勿随意转载,谢谢!

题目:

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

输入格式:

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

输出格式:

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

输入样例:

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

输出样例:

2
6
4
0

思路:

其实本题的解法有很多,可以用BFS(宽度搜索)一层一层地看。

例如,上面输入样例,可以画为:

(这里推荐一个在线画图网站:https://csacademy.com/app/graph_editor/

例如,当搜索节点1时:

会搜索2和3两个节点。但是题目要求,当距离一样时,输出标号最小的那个:

若这样的山头不只一个,则输出编号最小的那个

我认为这里可以有两种方法:

  • 搜索同一层时,记录标号最小的那个:可以记一个变量,利用min()函数维护这个变量。
  • 读入数据后,先将每一个节点的子节点分别按照从大到小的顺序排列,这样BFS按顺序处理后,同一层中最后一个节点就是我们想要的。

下面的代码中我用的是上面第二种方法。

其他的就是BFS的套路了,没啥可说的,都写注释了。


解法:

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;
vector<int> G[N]; // 记录每个节点的子节点
int vd[N]; // "visited"的缩写,标记是否被搜索过,默认0未搜索,搜索过记为1
int n;

int bfs(int u)
{
    if (G[u].empty()) {
        // 如果当前节点没有子节点,按照题意返回0
        return 0;
    }

    memset(vd, 0, sizeof(vd)); // 一些节点在其他节点可能被搜索过,但是管我这一轮搜索什么事,全部重置状态为未搜索过
    queue<int> q;
    q.push(u);
    int last; // 记录最后访问的节点,当这一轮循环结束后留下的即为最远层的编号最小的节点
    while (!q.empty()) {
        int tmp = q.front();
        vd[tmp] = 1;
        for (int v : G[tmp]) {
            if (!vd[v]) {
                q.push(v);
                last = v;
                vd[v] = 1;
            }
        }
        q.pop();
    }
    return last;
}

int main()
{
    int m, k;
    cin >> n >> m >> k;
    // 读入数据,建立各个节点的对应关系
    while (m--) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    // 将每个节点的子节点按照从大到小排序
    for (int i = 1; i <= n; i++) {
        sort(G[i].begin(), G[i].end(), greater<int>());
    }

    while (k--) {
        int a;
        cin >> a;
        cout << bfs(a) << endl;
    }

    return 0;
}
C++C语言BFS宽度搜索算法题解