A同学前两天在PTA上刷到7-102 喊山这道30分的题卡了大半天跑来找我救火。他代码写得不短样例输出也完全正确但一提交就飘红。我问他用的什么算法他理直气壮地说“DFS深搜到底找最远”。问题一下就找到了——题目里那个“最远”实际上要的是按传播层数计算的最短距离下的最远层。深搜这种一扎到底的遍历方式在环和叉路面前根本管不住距离而你需要的答案是bfs广度优先搜索加vector邻接表遍历每个节点时记录传播层数最后一层里挑编号最小的输出。这道题看起来是一个简单的图遍历模板但审题不仔细、建图漏边、多组询问不清空状态都足以让你从30分一路跌到十几分。我把这道题的题意、建模、代码、踩坑点从头到尾拆一遍附上能直接照抄的C实现顺便还原一次完整的问题排查过程希望对正在刷图论的你有帮助。1. 喊山的题面与建模从喊声扩散到无权图bfs1.1 题目到底在问什么喊山的题面不长。你站在某个山头把双手围成喇叭状大喊一声旁边的山头能同时听到这声喊接着旁边山头上的人也会继续向他们的邻居传话就这样一圈一圈往外扩散。题目给你n个山头、m条“相邻可闻”的关系以及k次询问每次问你从某个山头开始喊最终能传到的最远山头是谁。如果存在多个同样远的山头输出编号最小的那个如果这个山头喊了之后除了自己谁都听不到就输出0。输入格式很明确第一行是三个整数n、m、k接下来m行每行两个整数a、b表示a山头和b山头之间可以直接听到彼此。这m行之后是k个询问每个询问给一个起始山头编号。输出则是每个询问对应的最远山头编号换行分隔。这里有一个非常容易误解的地方题目要的不是“图上最长的简单路径”而是“喊声按层传播后能到达的最远那颗点”。喊一次就是往所有邻居传一次邻居再同时往外传所以传播距离本质上是无权图里的最短跳数而“最远山头”就是所有可达节点里最短跳数最大的那些点。这两个概念在带环图里差别很大深搜错就错在这里。1.2 为什么正解是bfs而不是dfs或最短路算法你把喊声扩散的过程画出来会发现它天然是分层的第0层 1 / \ 第1层 2 3 / \ 第2层 4 5起点是第0层和起点直接相连的山头是第1层第1层的邻居除去已访问的又是第2层……每一层都比上一层多一次传播。BFS的队列扩展顺序正好就是一层一层往外扫每个点第一次入队时的层数就是从起点到这个点的最短传播距离。谁的层数最大谁就是答案候选。为什么不能用DFS深搜讲究“一条路走到黑”它访问节点的次序受递归分支先后影响完全不符合“由近及远”的扩散语义。更致命的是如果某个节点先被一条长路径访问到并打上vis标记之后一条更短路径经过它时会被直接跳过这个点的距离就被永久地标错了。也有人会想那用Dijkstra单源最短路行不行行是行但没必要。Dijkstra处理的是带权图需要优先队列维护堆写法重、常数大。这道题所有边权重都是1用普通的队列bfs就能保证每个点第一次访问时层数最小代码简单得多跑得也更快。2. 用vector建图写bfs的完整实现2.1 建图方式怎么选这题的数据规模在PTA的常规区间内n、m、k一般都在10^4量级是一个典型的稀疏图。建图有三种常见选择建图方式空间复杂度码量适用场景邻接矩阵O(n^2)最低n很小、图很密vector邻接表O(nm)低中大规模稀疏图本题首选链式前向星O(nm)较高需要边编号、大量删边等特殊场景邻接矩阵在这题不可取n到1万时二维数组开1e8个布尔值内存直接爆炸而且只有m条边绝大多数格子是浪费的。链式前向星性能不差但对初学者来说头插法、next数组这些概念容易写错调试成本高。vector邻接表是最平衡的方案写起来直观内存只有O(nm)遍历邻居时用范围for一行搞定非常适合这类图论入门题。2.2 核心代码与逐行解释下面是一份可以直接提交的C17代码我加了解释#include bits/stdc.h using namespace std; vectorvectorint g; vectorint vis; int bfs(int s) { queuepairint, int q; q.push({s, 0}); vis[s] 1; int maxDepth 0; int ans 0; while (!q.empty()) { auto [u, dep] q.front(); q.pop(); if (dep ! 0) { if (dep maxDepth) { maxDepth dep; ans u; } else if (dep maxDepth u ans) { ans u; } } for (int v : g[u]) { if (!vis[v]) { vis[v] 1; q.push({v, dep 1}); } } } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, k; cin n m k; g.resize(n 1); vis.assign(n 1, 0); 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 x; cin x; fill(vis.begin(), vis.end(), 0); cout bfs(x) \n; } return 0; }为什么队列里存的是pair而不是单独开一个dist数组因为bfs天然按层扩展每个点的dep就是它首次入队时的层数。如果开dist数组每次扩展还要多一次数组访问用pair直接跟着点走逻辑更贴近“传播”这个行为读代码的人一眼就能明白。为什么答案更新要用dep和maxDepth去比而不是单纯记一个“最后一次出队的点”因为最后一次出队的点一定在最大深度但同一深度可能有多个点你需要在它们之间再按编号择优。起点本身深度是0它不参与答案统计所以代码里用if (dep ! 0)包住答案更新逻辑这样孤立点查询时ans会保持初始值0正好符合题目要求。2.3 手动推演一次bfs的完整过程光看代码可能不够直观我用手推一遍。假设输入是8 6 1 1 2 2 8 1 3 3 7 1 4 4 5 1这张图有三个分支8、7、5到起点1的距离都是2所以最远层是节点5、7、8正确答案应该输出编号最小的5。队列和答案变量的变化过程如下初始队列[(1,0)]maxDepth0ans0出队(1,0)邻居2、3、4按顺序入队队列[(2,1),(3,1),(4,1)]出队(2,1)dep1大于0maxDepth变为1ans2扩展出(8,2)出队(3,1)dep等于maxDepth但3不比2小不更新扩展出(7,2)出队(4,1)dep等于maxDepth4不比2小不更新扩展出(5,2)出队(8,2)dep大于maxDepthmaxDepth变为2ans8出队(7,2)dep等于maxDepth7比8小ans更新为7出队(5,2)dep等于maxDepth5比7小ans更新为5最终输出5。这个推演刚好演示了同层取最小编号的完整逻辑如果只在dep大于maxDepth时更新8就会一直被锁在答案上5和7都进不来输出就错了。3. 影响分数的四个隐藏细节3.1 无向边漏存一条题目里“相邻可闻”是双向关系a能听到bb也一定能听到a所以存边时必须写两行g[a].push_back(b); g[b].push_back(a);很多人在紧张状态下只写第一行把图变成了有向图声音就变成“单向传话”了。样例如果构造得巧恰好输入顺序和传播方向一致你能跑过样例但一旦遇到某条边方向反过来bfs就从那里断掉了。自检方法很简单构造只有两个节点一条边的图问一次1正常答案应该是2如果你输出0那八成就是漏存了反向边。3.2 多次询问的vis数组清理vis是全局数组每跑一次bfs都要恢复成未访问状态。最稳妥的做法是在每次询问前fill一遍fill(vis.begin(), vis.end(), 0);常见的低级错误是把这个fill写到while循环外面只清理了第一次后面每次询问vis里全都残留着之前的访问标记bfs一开始就把所有点当成已访问直接跳过导致后续询问全部输出0。第一次对、后面全错这种“部分正确”的分数表现非常典型排查时一定要先看清理语句的位置。3.3 最深层多个节点时选编号最小同一层可能有多个山头比如一个十字路口两头都能传到。题目要求如果距离相同输出编号最小的那个。这意味着你的答案更新逻辑必须同时维护两个优先级深度优先编号次之。对应到代码就是开头那一段if (dep maxDepth) { maxDepth dep; ans u; } else if (dep maxDepth u ans) { ans u; }如果只写dep大于maxDepth时的更新同层节点中后访问的小编号点就永远没有机会替换先访问的大编号点。这种错误样例通常很难暴露因为样例的图往往是链状的根本不存在同层多点。建议自己额外构造一个星形或菱形图去测。3.4 孤立点与“自己不算目标”如果一个山头周边一个相邻山头都没有bfs只会访问起点自己。起点深度0不参与答案更新ans保持初始值0最后输出0这正好是题目要求的“传不到其他山头就输出0”。但如果你在实现时不小心让起点的dep0参与了答案更新比如把条件写成了dep maxDepthans就会被更新成起点本身。题目要的是“最远的其他山头”自己传给自己不算传播所以这种写法在孤立点用例上必挂。这里的if (dep ! 0)判断不是锦上添花是必要条件的防线。4. 一次从部分正确到满分的完整排查过程4.1 深搜版本为什么样例能过、提交却错A同学最初的版本是DFS加vis样例过得很轻松。我给他构造了一个反例4 4 1 1 2 2 3 3 4 1 4 1这个图里1和4直接相邻同时1又通过2、3和4连成一条链。按正确的含义1到4的距离是11到3的距离是2所以最远点应该输出3。但深搜的顺序是递归里先走的邻居决定的。假设从1先走向2递归就会一路扎到1-2-3-4在第3层就把4的vis标记设置好等递归回到1再走到4那条直接边时vis[4]已经是true直接跳过。这时候DFS记录的“深度”里4变成了深度33的深度是2程序会误以为4是最远的输出4正确值3反而丢了。这就是深搜在无权图距离问题上的典型陷阱它不能保证首次访问某个点的路径是最短路径一旦先走了一条长路这个点就被“污染”了。4.2 逐项排查的思考链换掉DFS后A同学从WA变成了部分正确于是我们开始从头过逻辑。排查的顺序是这样一条链先验证建图。我把测试数据改成两个人两个山头1和2问1正确输出2。他跑出来正确说明双向边建了排除3.1。再验证vis清理。我连续给出三次询问第一次1第二次还是1第三次还是1。结果第一次对后两次都输出0问题立刻暴露vis在询问间没有被重置第二次bfs直接跳过所有点。把fill挪到每次询问前这部分修复。再验证答案选择。我构造了前面那个三分支图正确输出5他输出8。定位到答案更新逻辑只处理了dep大于maxDepth的情况没有处理dep等于maxDepth时取更小编号。补上else if分支后输出变正确。最后验证孤立点。单独构造一个只有节点1且没有边的图问1正确输出0。他此时输出也是0说明起点不参与答案更新这个细节没有踩坑。四个环节全部过完提交才从部分正确变成满分。这个例子非常典型我建议大家以后遇到“样例能过、提交部分正确”的图论题也按这个顺序排查建图方向、vis清理、答案选择、边界输入。大多数丢分都藏在这四个点里而不是藏在算法本身。5. 复杂度边界与更省事的优化写法5.1 O(k(nm))到底行不行单次bfs会把每个点访问一次每条无向边扫描两次复杂度O(nm)。题目有k次询问所以整体最坏是O(k(nm))。以n、m、k都在10^4量级来算最坏大约2e8次简单操作C的队列加vector遍历在PTA的时限下通常能跑过所以直接写暴力版本的bfs并不是罪过。但如果你追求稳妥有两个小优化值得做。第一个是提前剪枝每次bfs统计访问的节点数如果某个询问的起点所在连通分量只有一个点那么访问次数为1答案一定是0不需要继续扩展。第二个是减少清空代价下面单独说。5.2 用时间戳省掉memset每次询问前fill一遍vis数组代价是O(n)。k次询问就是O(kn)在数据接近上限时会额外增加1e8次操作。时间戳是竞赛里非常经典的做法本质是把vis从“布尔值”改成“int时间标记”每次bfs先增加一个tag计数器访问节点时判断vis[v]是否等于当前tagvectorint vis; int tag 0; int bfs(int s) { tag; vis[s] tag; queuepairint,int q; q.push({s, 0}); int maxDepth 0, ans 0; while (!q.empty()) { auto [u, dep] q.front(); q.pop(); if (dep ! 0) { if (dep maxDepth) { maxDepth dep; ans u; } else if (dep maxDepth u ans) { ans u; } } for (int v : g[u]) { if (vis[v] ! tag) { vis[v] tag; q.push({v, dep 1}); } } } return ans; }这样一来清空vis的操作从O(n)降到了O(1)只是概念上稍微绕了一点竞赛时间充裕时值得掌握。另外还有一种“逐层队列”的写法用两层循环外层标记当前深度内层用q.size()控制只处理当前层的节点这样代码会天然把“层”包装起来适合教学展示但实际跑起来需要额外vector暂存当前层点道理和pair写法完全一致就不多写了。5.3 个人刷题经验我在实际刷这题的过程中最大的体会是喊山考的根本不是会不会写bfs模板而是能不能把一个生活场景准确地翻译成图模型。翻译对了剩下的都是背过的模板翻译错了DFS写得再花哨也是白搭。以后只要遇上“最短”“最远”“传播”“扩散”这类词先条件反射地联想到按层展开然后动手画一张小图把层号标在旁边再开始写代码。这个习惯帮我避开了很多看似玄学的部分正确也推荐给你试试。