第一次在PTA上刷到7-102这道题“喊山”两个字就很有画面感——一个人站在山头上双手围成喇叭状对着远方的山大声喊声音沿着山路一层一层往外传。剥开这层壳它其实是一道非常经典的图论题核心解法就两个词BFS、vector。这道题在PTA里占了30分属于典型的“看着唬人、想通了就很简单”的题目。它考察的东西很直接无向无权图的单源最短路径思想以及用邻接表存图、用广度优先搜索逐层扩散的基本功。对于正在学图论、准备考数据结构期末或者刷算法题的同学来说这道题是一道性价比很高的练习题——不是那种绕弯子的难题但能把BFS的几个关键细节全部串起来图的存储、队列的使用、dist数组的维护、答案的选取、边界条件的处理。这篇文章我就围绕这道题把完整的思路、代码实现、踩坑经历全部过一遍。不管你是一看BFS就头疼的新手还是想快速确认自己写法有没有问题的老手这篇解析应该都能给你一点参考。1. 题目到底在问什么先拆掉“喊山”这层壳1.1 原题背景与真实考点题目描述里通常会写一段背景某个山区的山之间有小路一个人站在某座山上喊话喊声会沿着山路向外传播。每经过一条山路就算传播了一层。问的是从给定的起点山头喊出去最远能传到哪座山如果最远的山头不止一个输出编号最小的那个如果除了自己一座山都喊不到输出0。把背景全删掉剩下来的就是一句人话在无向无权图上给定起点s求出所有能到达的节点里距离s最远的节点是谁距离相同的选编号最小的若没有其他可达节点输出0。这里有一个关键点很多人没意识到题目里的“山路”每一条都是等价的没有长度、没有权重走一步就是一步。这正是它能用BFS解决的先决条件。如果哪一天题面改成“每条山路长度不同”那BFS就得换成Dijkstra复杂度完全不是一个量级。所以在读题的时候第一时间就要判断出“权”到底存不存在。1.2 数据范围与算法选型PTA这道题的山数、路数和询问次数虽然没有在标题里写出来但从它出现在数据结构图论章节、占30分来看规模基本是往大了给的。常见的情况是n、m、k都在10^3到10^4这个量级单次询问跑一遍BFS的代价是O(nm)所有询问加起来是O(k*(nm))。这个复杂度在C里是能接受的。有些人可能会想既然有多次询问为什么不一次性预处理所有点对之间的最短路比如跑n次BFS或者n小的时候直接Floyd。这个思路没问题但在这道题里属于过度设计。题目设置的询问次数通常不会大到让“每次独立BFS”超时的程度而且PTA的评测数据往往就是为了考察你能不能把BFS写对而不是让你写一个全源最短路算法出来。先把每次BFS写对再谈优化这才是刷题的正确顺序。1.3 为什么不能用DFS看到“最远”两个字有人第一反应是用DFS递归地往深处走记下最大深度。但DFS在无权图上有一个致命问题——它不保证第一次访问到某个节点时走的是最短路径。比如从起点出发一条路是直通目标节点但绕远另一条路是两步到达但DFS可能先走了远路导致dist被记成一个很大的值后面即使走到了更短的路径再想去更新就晚了。除非你写成“允许重复访问不断更新最小深度”的暴力DFS那复杂度会爆炸。BFS就没有这个问题。它天然按层扩散第一次访问到某个点时走的路径一定是最短路径这是BFS最重要的性质。所以看到“最少步数”“最远可达”“最短路径”这类字眼第一反应应该是BFS而不是DFS。2. BFSvector解题思路的完整拆解2.1 从“传播层数”到“最短距离”的转换BFS的核心思想是逐层扩散。假设起点是s先把s放入队列然后取出s遍历s的所有邻居这些邻居就是距离为1的节点接着取出这些邻居再遍历它们的邻居那些没有被访问过的节点就是距离为2的节点。整个过程就像水波一圈一圈往外荡。在这个过程里每个节点第一次被访问时的层数就是它到起点的最短距离。用一个dist数组记录这个层数即可。dist[s] 0s的直接邻居dist 1邻居的邻居dist 2依此类推。BFS结束之后dist数组里就存好了从起点到所有可达节点的最短步数。注意一个细节BFS一定要在“把节点入队的时候”就标记dist而不是在“出队的时候”标记。如果你在出队时才标记同一个节点可能会被多个邻居重复入队队列里出现冗余虽然最终结果可能还是对的但效率会变差极端情况下甚至会把复杂度拖高。最稳妥的写法就是当发现某个邻居v还没访问过时立刻设置dist[v] dist[u] 1然后入队。这一步是BFS代码最容易写错的地方。2.2 用vector建邻接表存图的方式有几种邻接矩阵、链式前向星、vector邻接表这道题首选vector邻接表。理由很直接n的规模不算大vector的开销可以接受代码写起来最简单遍历一个节点的所有邻居就是一层for循环不容易出现链式前向星那种数组越界或者头插法搞错的低级问题。建图的时候要注意是双向边。山路是能来回走的所以输入一条a-b的边要同时往g[a]和g[b]里push对方。具体来说vectorvectorint g(n 1); for (int i 0; i m; i) { int a, b; cin a b; g[a].push_back(b); g[b].push_back(a); }这里g的大小开成n1是为了让下标1到n都能直接用不需要做减一操作。节点编号从1开始是PTA这类题目的常见设定如果你从0开始存后面的遍历和输出都容易出错特别是有多个询问的时候。2.3 答案选取最远且编号最小BFS跑完之后你手里的dist数组记录了起点到所有可达点的最短距离。题目要的是距离最远的那个点如果有多个距离一样远的选编号最小的。这个“编号最小”是一个很容易被忽略的细节。很多人写代码的时候只记录最大距离忘了在距离相等时比较编号结果就错了。正确处理方式是在统计答案时不仅要看dist[i]是否更大还要在dist[i]等于当前最大距离时看i是否比当前答案编号更小。再有一个隐含条件起点自己不在答案候选里。如果只有起点自己可达那应该输出0。所以遍历的时候必须跳过i s的情况。2.4 时间复杂度与空间复杂度单次BFS的时间复杂度是O(n m)因为每个节点最多入队一次每条边最多被检查一次。k次询问就是O(k*(nm))。空间方面邻接表存储所有边需要O(n m)dist数组需要O(n)队列最坏情况下也只需要O(n)。总空间复杂度是O(n m)。这个复杂度在题目给定范围内是完全没问题的。如果k特别大比如每个点都要问一次那总复杂度变成O(n*(nm))如果n是10^4m是10^5那就到了10^9量级比较悬。但PTA这道题不会这么丧心病狂正常写BFS就能过。真遇到那种数据你再考虑预处理全源最短路也不迟。3. 核心代码实现一份能直接提交的C解法3.1 数据结构定义你需要三个核心数据结构gvectorvector 存图distvector 记录每个节点到起点的最短距离初始化为-1qqueue BFS用的队列。dist初始化为-1除了表示“未被访问”还有一个额外好处在最后统计答案时可以直接用dist[i] -1来判断这个节点不可达不需要额外开一个vis数组。本质上vis数组和dist数组合二为一了少一个数组就少一份出错的概率。3.2 完整代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin n m k; vectorvectorint g(n 1); for (int i 0; i m; i) { int a, b; cin a b; g[a].push_back(b); g[b].push_back(a); } while (k--) { int s; cin s; vectorint dist(n 1, -1); queueint q; dist[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (int v : g[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } } int maxDist -1; int ans 0; for (int i 1; i n; i) { if (i s || dist[i] -1) continue; if (dist[i] maxDist) { maxDist dist[i]; ans i; } else if (dist[i] maxDist) { if (i ans) { ans i; } } } if (maxDist -1) { cout 0 \n; } else { cout ans \n; } } return 0; }3.3 关键步骤逐行解读第1步读入n、m、k。n是山的数量m是路的数量k是询问次数。这个顺序在题目描述里一般是给定的注意别把k和m读反了。第2步建图。每一行输入一条路的两个端点a和b分别在g[a]和g[b]里加入对方。无向图的双向加边是必须的。第3步进入询问循环。每次询问重新初始化dist和队列。这里有个很多人会犯的错——把dist定义成全局数组然后在循环里忘了重置。如果你的dist是全局的每次BFS前必须用fill或者重新赋值把所有位置恢复成-1。用vector dist(n 1, -1)在循环体内定义可以天然避免这个问题。第4步BFS主体。从s开始dist[s]设置为0。只要队列非空就取出队首u遍历u的所有邻居v如果v没被访问过就更新dist[v] dist[u] 1并把v入队。这里对应的是“声音传播到下一座山”。第5步统计答案。遍历1到n跳过起点和不可达节点。找到dist最大的节点如果出现相同的dist保留编号更小的。用一个maxDist变量记录当前遇到的最大距离初始化为-1这样能区分“没有其他可达节点”的情况。第6步输出。如果maxDist仍然是-1说明除了起点没有能到达的山输出0否则输出ans。3.4 手动跑一个样例加深理解假设输入6 5 1 1 2 2 3 1 4 4 5 5 6 1图的结构是1连着2和42连着34连着55连着6。从1开始BFSdist[1] 0队列 [1]弹出1遍历邻居2和4dist[2] 1dist[4] 1队列 [2, 4]弹出2遍历邻居1和31已访问dist[3] 2队列 [4, 3]弹出4遍历邻居1和51已访问dist[5] 2队列 [3, 5]弹出3邻居2已访问无操作弹出5遍历邻居4和64已访问dist[6] 3队列 [6]弹出6邻居5已访问队列空结束。最终dist数组是0、1、2、1、2、3。最大距离是3对应节点6所以输出6。这跟直觉完全一致从1出发最远能传到6中间隔着3条路。4. 常见问题与排查技巧实录4.1 编号从1开始还是从0开始这是一个很低级但杀伤力极大的坑。如果你把vector开成n1大小却写成了for (int i 0; i n; i)那你的dist数组就没有统计编号为n的那个节点反过来如果你开成n大小却把输入的节点编号直接用遇到编号为n的节点就会越界。我的建议是统一从一开始到nvector开n1遍历也写for (int i 1; i n; i)一次性把所有边界都理顺。4.2 多组询问时dist和queue必须重新初始化每次询问都是独立的一次BFS上来先把上次的访问痕迹清干净。我用的是在循环内部定义vector和queue每轮循环都会重新构造天然没问题。如果你把dist定义成全局数组那么每次BFS前至少要做一次fill(dist.begin(), dist.end(), -1)不要漏。漏一次第二次询问的答案就会沿用上一次的dist出现各种匪夷所思的结果。4.3 输出0的边界条件到底怎么判断题目要求“传不到任何山的时候输出0”。这个词面很容易让人想成“最远距离是0就输出0”。但是注意起点自己的dist就是0如果不排除起点你会在统计时找到dist为0的起点然后输出一个错误的编号。判断逻辑必须包含两步一是排除起点二是排除不可达节点dist[i] -1。如果剩下的节点一个都没有maxDist就是-1这时候输出0才正确。我见过很多WA代码问题都出在这里——他们不排除起点导致n1或者s是孤立点时直接输出了s本身而不是0。4.4 用cout提速取消同步那两行必须写PTA的输入输出量在这种多次询问的题目里不算小尤其是k很大的时候。C的cin/cout默认会和C的stdio同步性能会打折扣。在main开头加这两行能明显提升速度ios::sync_with_stdio(false); cin.tie(nullptr);如果你不写也不是一定超时数据小的时候能过但没必要赌。养成习惯凡是涉及大量输入输出的题这两行直接写上。如果你的代码风格更偏C也可以用scanf和printf来写混用的时候不要关同步否则有潜在问题。4.5 为什么有的人用DFS也能过有些场景下DFS配上一个全局深度数组也能输出正确结果但那是数据水或者图恰好有特殊结构。真正严格意义上在无权图上求最远可达点DFS不是正确算法因为它不保证“第一次访问”就是“最短路径”。如果图里存在一条长路径先到达某个点DFS记录了一个很大的深度之后即便有一条更短的路径到达该点DFS也不会回头更新——除非你写了回头更新的逻辑那复杂度就失控了。所以不要看到网上有人说“我DFS也过了”就跟着学。那道题可能数据弱或者他的DFS恰好碰对了顺序。最稳妥的永远是BFS。4.6 常见问题速查表症状可能原因解决办法输出0的情况输出成了起点编号统计答案时没有排除起点遍历时加上 if (i s) continue第二次询问开始结果全错dist数组没重置每轮BFS前重置dist为-1数组越界或运行时错误vector大小开成n而不是n1统一开n1下标从1开始结果距离明显偏大出队时才标记dist导致重复入队改为入队时设置dist并标记超时cin/cout同步开销大加ios::sync_with_stdio(false)和cin.tie(nullptr)最远点选错距离相等时没有比较编号在dist[i] maxDist时取更小编号5. 从这道题延伸出去的几点体会刷完这道题有几个经验我是实打实留在脑子里的。一个是BFS的“入队即标记”这个习惯后来我写任何BFS题都条件反射地遵守再也没出现过重复入队导致的诡异问题。另一个是对“最远”这类需求的第一反应先问自己边的权重是不是1如果是那大概率就是BFS如果不是再想Dijkstra那一套。这种条件反射不是看几篇题解就能建立的必须上手写、写错、再对比才能真正长在身上。我这段时间刷PTA的数据结构题明显感觉到7-102这道题的位置安排是很讲究的。它不考什么奇技淫巧就是踏踏实实地考你有没有把BFS的基本功打牢。你要是能不看任何参考独立把这题一遍写对说明你的图和队列基础已经比较稳了要是边写边卡、改了又改那正好借这个机会把BFS的几个关键细节彻底理清楚。如果你接下来还想继续练同类题目可以找那些同样是无向图、要求最短路或者连通性的PTA题目做对比。你会发现很多题看起来换了五花八门的背景从“喊山”换成“迷宫”“网络”“社交关系”剥开外壳之后的核心解法其实都是同一个BFS。把这个模型吃透了以后碰到的很多图论入门题都不用慌。