1. 危险系数到底是道什么题先把题目读懂做DFS练习的人应该都有这种感觉前面练了几道套路题比如全排列、迷宫可达性、连通块数量套路都熟了突然翻开练习2看到危险系数四个字第一反应是——这跟DFS有什么关系先把这个题彻底说清楚。题目原型来自某竞赛题库大意是这样的给定一个无向图有 N 个节点编号 1 到 NM 条边。再给定两个节点 u 和 vu ! v。如果从 u 到 v 至少要经过某个节点 ww 不等于 u 也不等于 v也就是说一旦把节点 w 删掉u 和 v 之间就变得不可达那么 w 就称为危险系数贡献点。题目要求你统计从 u 到 v 的所有可能路径中到底有多少个节点是必经节点输入格式一般是N M 接下来 M 行每行两个整数 a b表示 a 和 b 之间有一条无向边 最后一行 两个整数 u v输出就一个整数危险系数也就是必经节点个数。我见到这个题的第一反应是这不就是个割点题吗用 Tarjan 求割点不就行了但细想不对——Tarjan 求的是整张图的割点而这个题只关心从 u 到 v这个范围内的必经节点。比如说图的另一边有个割点跟 u 到 v 的通路毫无关系它就不是危险节点。所以这个题本质上是带起止点限制的动态割点判定不能直接套模板。那为什么把它放在 DFS 练习里因为这个题有一个非常朴素的解法思路既然我要判断从 u 到 v 的所有路径中某个节点是不是每条路径都会出现那我干脆把从 u 到 v 的所有路径都枚举出来统计每个节点在这些路径里出现的次数。如果某个节点出现了路径总数那么多次也就是每条路径都经过它那它必然是危险节点。你看这不正是 DFS 最天然的应用场景吗DFS 就是用来沿路走到黑、回溯再换路的。枚举所有路径这件事简直是为 DFS 量身定做的。不过这里有个很现实的问题路径枚举在最坏情况下是指数级的。所以做题之前得先看数据范围。我见过的版本里N 一般不超过 1000M 也是稀疏图级别的数据量而且实际测试数据中,u 到 v 的路径数量并不会爆炸到不可收拾暴力枚举路径才可能通过。这道题放在 DFS 练习里本身就暗示了出题人希望你走这条最直白的路而不是先去学 Tarjan。2. 先别急着写代码把必经节点翻译成可计算的判定条件2.1 数学化表达路径集合与出现次数在动手写 DFS 之前我用了一个晚上的时间想清楚了这个问题的本质是的第一次写我直接敲代码结果统计条件写错了浪费了大半天。其实可以这样定义设从 u 到 v 的所有简单路径简单路径就是路径中不重复经过节点构成一个集合 P。假设一共有 K 条路径P { path_1, path_2, ..., path_K }对于某个节点 w定义 f(w) 为 w 在这 K 条路径中出现的次数。那么如果 f(w) K说明每条路径都带了 w 这个乘客w 就是必经节点。如果 f(w) K说明至少有一条路径绕开了 w那删掉 w 不影响 u 到 v 的连通性w 就不是危险节点。这里有个容易忽略的细节u 和 v 本身也会出现在每条路径里所以如果不加过滤起点和终点必然会被统计成每条路径都出现那就错了。题目的危险系数明确排除了起点终点所以最后统计时要跳过 u 和 v。如果你想把这个判定条件证明得更严谨可以用反证法如果 w 不是必经节点那就存在一条 u 到 v 的路径不经过 w那么 f(w) 就不可能等于 K反过来如果 f(w) K说明每条路径都有 w一旦删掉 w每条路径都被截断u 和 v 自然不可达。2.2 为什么必须枚举所有路径而非一条可行路径这里有一个很多初学者会跳进去的坑一开始想的是我先随便找一条 u 到 v 的路径然后把这条路径上的点全当成危险节点——这显然不行。因为危险系数的定义是在所有路径中都出现的节点而不是某条路径中出现的节点。举个例子图长这样1 - 2 - 4 \ | \ | \ 3 \| 5 | 6起点是 1终点是 4。从 1 到 4 的路径至少有1 - 2 - 41 - 3 - 41 - 2 - 3 - 4如果有 2-3 这条边的话在这个图里节点 2 虽然在第一条路径里出现但它在第二条路径里没出现所以 2 不是危险节点。只有那些稳稳当当出现在每一条路径里的节点才是危险节点。再比如一个更直观的例子一个哑铃形图u 和 v 分别在两头中间只有一个桥接节点 w 连接两个完全分离的子图。那从 u 到 v 无论怎么走都必须路过 ww 就是危险节点。这种情况下的危险系数至少为 1如果中间不止一个串联节点那每个串联点都是危险节点。所以题目翻译成算法就是遍历完从 u 到 v 的所有简单路径期间做累计计数最后比对计数和总路径数。听起来简单实现起来有几个坑我下面一节详细说。3. DFS 枚举路径的完整实现邻接表、回溯标记、路径记录3.1 数据结构选择邻接表而不是邻接矩阵这种题老老实实用邻接表存图。很多新手习惯用二维数组int g[N][N]表示邻接矩阵简单直观但两个问题会让你很痛苦N 1000 时邻接矩阵要开 1000×1000 的 int100 万个 int 大概是 4MB这倒还好但遍历的时候会多出很多无效邻居判断。用 DFS 枚举路径时你要循环检查每个节点是不是当前节点的邻居如果用邻接矩阵每次if (g[cur][i])要扫 N 次用邻接表只扫真实的邻居个数。在路径枚举这种高频操作里性能差距不是一点半点。我用vectorvectorint来存邻接表。C 里这样写vectorvectorint adj(n 1); // 1-based 编号 for (int i 0; i m; i) { int a, b; cin a b; adj[a].push_back(b); adj[b].push_back(a); // 无向图双向加边 }3.2 核心递归函数设计记录路径、标记访问、回溯恢复DFS 枚举所有路径的核心思路是从起点 u 出发每次走到一个未访问过的邻居把它加入当前路径如果走到了终点 v就把当前路径登记下来否则继续往下递归。递归返回后把该节点从当前路径弹出并把访问标记复位——这一步就叫回溯。这里有一个特别容易犯的错递归进入下一个节点之前标记访问回溯回来后必须取消标记。如果忘了取消标记后面就再也不能从这个节点经过路径数会少算如果在错误的位置取消标记又可能造成一个节点在单条路径里重复出现形成环。我推荐的标准写法vectorint path; // 当前路径 vectorint vis(n 1, 0); // 访问标记 int totalPaths 0; // 路径总数 vectorint cnt(n 1, 0); // 节点在路径中的出现次数 void dfs(int cur, int target) { if (cur target) { // 到达终点登记这条路径 totalPaths; for (int node : path) { cnt[node]; } return; } for (int nxt : adj[cur]) { if (!vis[nxt]) { vis[nxt] 1; path.push_back(nxt); dfs(nxt, target); path.pop_back(); // 回溯恢复路径 vis[nxt] 0; // 回溯恢复访问标记 } } }调用入口vis[u] 1; // 起点先标记 path.push_back(u); // 起点加入当前路径 dfs(u, v);注意这里起点在递归前就标记好并加入路径因为终点判断在进入dfs时就检查如果起点也是终点题目保证u ! v一般不会有但以防万一也能正确处理。细心的读者会问递归到终点时path里已经包含了v吗会的。因为我们在dfs(nxt)之前就push_back(nxt)了 nxt当nxt恰好是v时下一次递归一进来cur target成立这时path里最后一位就是v。所以统计cnt时起点终点都被算进去了最后过滤即可。3.3 主函数和危险系数统计路径枚举完毕后危险系数的计算只需要一次遍历int danger 0; for (int i 1; i n; i) { if (i u || i v) continue; // 排除起点终点 if (totalPaths 0 cnt[i] totalPaths) { danger; } } cout danger endl;这里totalPaths 0的判断特别重要。如果 u 和 v 本来就不连通totalPaths 0此时如果不加判断cnt[i]也全是 00 0为真所有节点都会被误判为危险节点输出 N-2那可就错得离谱了。这个坑我在别的题目里踩过类似的所以特别强调一下。完整代码合起来是这样#include bits/stdc.h using namespace std; vectorvectorint adj; vectorint path; vectorint vis; vectorint cnt; int totalPaths 0; void dfs(int cur, int target) { if (cur target) { totalPaths; for (int node : path) { cnt[node]; } return; } for (int nxt : adj[cur]) { if (!vis[nxt]) { vis[nxt] 1; path.push_back(nxt); dfs(nxt, target); path.pop_back(); vis[nxt] 0; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; adj.resize(n 1); vis.assign(n 1, 0); cnt.assign(n 1, 0); for (int i 0; i m; i) { int a, b; cin a b; adj[a].push_back(b); adj[b].push_back(a); } int u, v; cin u v; vis[u] 1; path.push_back(u); dfs(u, v); if (totalPaths 0) { cout 0 endl; return 0; } int danger 0; for (int i 1; i n; i) { if (i u || i v) continue; if (cnt[i] totalPaths) { danger; } } cout danger endl; return 0; }4. 我是怎么一步步排查出统计偏差的一次完整的踩坑实录光给最终代码不算完我把自己第一次写这道题时踩的坑完整复盘一遍。这个过程比代码本身更有价值——因为很多人看题解觉得就这么简单结果自己写出来就是不对。我第一次写的时候DFS 函数长这样void dfs(int cur, int target) { if (cur target) { totalPaths; for (int node : path) cnt[node]; return; } vis[cur] 1; // 注意这里我在这里标记 for (int nxt : adj[cur]) { if (!vis[nxt]) { path.push_back(nxt); dfs(nxt, target); path.pop_back(); } } vis[cur] 0; }看起来挺对称的对吧但运行出来的结果在好几个测试用例上都差 1 到 2。我当时还以为是起点终点过滤的问题检查了半天后来用一个小图手工模拟才发现问题所在当我把vis[cur] 1放在进入递归之后马上执行时终点 v 也会被标记。而终点 v 标记后在终点处直接 return不再继续扩展这没问题。但问题出在如果图中有另一条路径也需要经过 v当然这不可能因为 v 是终点路径到 v 就结束了——等等这样想其实还是没想到点上。真正的问题在于start 节点 u 的访问标记在递归开始前已经设了 1但如果在dfs内部再对cur设置一次当从某个分支回溯回来时如果这个节点还在当前路径的前缀中标记并不会丢失但如果你把设置标记和取消标记放在递归函数内部有的分支顺序会导致标记错误地提前清除。我模拟一个具体的三角形图1-2-3-1u1, v3。路径为1 - 2 - 31 - 3用我的错误写法dfs(1): vis[1]1 邻居2: vis[2]0, push 2, dfs(2) dfs(2): vis[2]1 邻居1: vis[1]1, 跳过 邻居3: vis[3]0, push 3, dfs(3) dfs(3): vis[3]1 curtarget, 统计路径 [1,2,3], total1 return pop 3 vis[3]0 ... pop 2 // 此时 vis[2]0 邻居3: push 3, dfs(3) dfs(3): vis[3]1 curtarget, 统计路径 [1,3], total2 return pop 3看起来这个例子恰好是对的。但换一个稍微复杂的图1-2-41-3-42-3 也有边u1, v4。所有路径包括1-2-4, 1-2-3-4, 1-3-4, 1-3-2-4。在错误写法里某个分支的标记清除时机不对会导致某些路径被重复统计或漏统计。说白了在最规范的回溯写法中访问标记应该紧挨着push_back设置紧挨着pop_back取消两两配对不要拆开放在递归函数的不同位置。否则你很难直观地验证标记状态和路径状态的同步性。标记状态代表从起点到当前节点的搜索栈里包含了哪些节点路径数组代表的是同一件事两者必须始终一致——想明白这一点你就能理解为什么规范写法是那样的了。4.1 还有一种隐蔽的重复路径问题平行边如果输入数据里出现平行边——比如 1 和 2 之间有两条边那么 DFS 会分别走这两条边产生两条路径一条经过第一条边一条经过第二条边。从图论角度这两条路径的节点序列完全相同但边不同。危险系数关心的是节点重复路径会导致 totalPaths 变大但 cnt 也同步变大最终每个节点的比值其实没变其实不是——如果两条平行边构成了两条不同的路径cnt 会重复累计但比值可能仍然相等危险系数结果碰巧不受影响。但如果出题人数据里包含平行边而我刚才的统计方式会认为存在多条路径把 2 算成必经节点实际上从节点连通性来说 2 依然是唯一的桥结果碰巧一致。不过为了稳妥我一般会在建图时去重平行边或者先问清楚题目约定。大多数这类题目会保证没有平行边但自己实现时知道这个坑总是好的。4.2 自环问题自环就是a b的边。如果起点或终点的邻居里有自己DFS 会尝试走cur - cur但因为vis[cur] 1会被挡住不会造成死循环。但如果你的代码写的是先判断cur target再检查访问标记一个自环并不会导致错误只是白白多走一次判断。真正危险的是如果自环出现在中间节点且你忘了标记访问那就会无限递归下去。所以访问标记一定要在递归调用之前设置这基本是铁律。5. 复杂度与优化为什么这道题的暴力枚举能过以及什么时候必须换思路5.1 最坏情况下的指数复杂度到底能不能接受我不骗你DFS 枚举所有路径的最坏复杂度是 O(2^N) 级别的。在完全图中从任意一点到另一点的简单路径数量是接近阶乘级的N20 就能让任何机器瞬间卡死。但这类题能过依赖的往往是数据范围约束。假设 N 1000M 2000虽然节点很多但边稀疏每个节点的实际度数很小从 u 到 v 的路径数量不会爆炸。用 DFS 跑一遍实际运行时间基本在几十毫秒到几百毫秒之间。我做过的数据里路径数量最多也就几万条每条路径长度平均不到几百个节点总操作量在千万级别完全能扛住。如果你的测试数据里 N 到了 1000而且图构造得很刁钻比如中间有一大堆并行的链路径数量指数爆炸DFS 会超时。这时候不要硬扛可以考虑两条优化路线双向搜索从 u 正向 DFS从 v 反向 DFS记录路径前缀/后缀的交点信息。但实现起来很繁琐而且对于这个必经节点判定问题来说仍然需要处理交集统计并不优雅。转成动态割点问题先求所有割点再用某种方式判断割点是否位于 u 和 v 之间。但这里有个复杂点——位于 u 和 v 之间并不等价于割点在连通块边界上还是需要额外处理。说实话练习题的定位就是让你感受 DFS 的暴力美学不建议为了性能把代码复杂化。只要确认数据范围合理直接枚举路径是性价比最高的解法。5.2 从枚举全部路径到只统计计数每一条路径都要完整登记吗还有个性能优化点其实不需要真的存储每条路径的完整序列。当前代码的做法是到达终点后把 path 里的每个节点遍历一遍累加 cnt这需要对路径长度求和。如果路径数多、路径长这段的开销甚至可能超过 DFS 本身。一种常见的优化是在 DFS 进入每个节点时立刻累加 cnt回溯时不做减法但用路径数增量来区分。也就是说每进入一个节点就先把该节点的 cnt 加 1表示当前这条路径包含了这个节点。等到达终点时totalPaths 加 1表示完整路径数。这样做虽然每个节点的计数仍然会累加很多次但省去了到达终点后的二次遍历。不过要注意这种进入即累加的方式如果没有配合回溯时的路径结束判定会出现走到了死路但计数已加的问题。所以更稳妥的做法还是到达终点后再统一累加牺牲一点性能换取逻辑清晰。我在实际比赛中用的就是到终点后统一累加因为路径总数和路径长度的乘积在数据范围内真的不大代码可读性第一。5.3 判断危险节点的另一种视角路径唯一性如果你已经枚举出所有路径还有一种等价的判定方式某个节点 w 是危险节点当且仅当从 u 到 v 的路径中w 在所有路径上出现的位置形态完全一致比如 w 前面经过的节点集合相同。这个视角看起来更高级但要实现反而更复杂不如直接比较 cnt 比值来得简单——这说明直白的统计往往比花哨的证明更实用。6. 从这道练习2延伸出来的核心心法DFS 回溯的进入/离开对称性练完这道题我最大的收获不是我会做危险系数了而是对 DFS 回溯的整体理解上升了一个台阶。如果你也是刚开始刷 DFS 的题下面几点心得应该对你后续做题很有帮助。6.1 记住进入做什么、离开还原本这个模式任何一个 DFS 搜索树的节点都有两个关键时机进入节点时入栈和离开节点时出栈。进入时需要做的标记节点已被访问、把节点加入当前路径、累加某种计数。离开时需要做的移除路径、恢复访问标记、撤销计数影响。你可以把 DFS 想象成一个人走进迷宫每走一步就在地上摆一个标记物占位离开这个岔路口时把标记物收走这样别的岔路才能借用这条通道。如果你摆下标记物却没收走别的路径就会以为这条路有人占着导致漏掉很多可能性如果你压根没摆标记物就会原地打转陷入死循环。这套进入/离开对称性是所有回溯题的通用骨架。后面你遇到全排列、组合总和、N 皇后、单词搜索全是这个小模式的变体。危险系数练的就是这个骨架所以它作为 DFS 练习第二题非常合适。6.2 当前路径集合要始终与访问标记集合保持一致我一直建议写 DFS 时把path和visited两个数据结构当作同一个东西的两种表达。当你向path.push_back(x)时立刻visited[x] 1当你path.pop_back()时立刻visited[x] 0。这个规则在任何情况下都不要打破。如果你把标记访问和加入路径拆开放在不同的逻辑分支里等到代码复杂了标记状态和路径内容就会悄悄失去同步最后出现一些神仙都查不出来的 Bug。我的排查经验是这类 Bug 通常表现为答案偏大或偏小但路径总能找到非常隐蔽。6.3 终点处理要先行起点标记要提前递归函数的开头第一件事就是判断是否到达终点而不是先做当前节点合法检查。这样做的好处是你可以在调用dfs(nxt)之前就push_back(nxt)不需要在终点处再手动把终点加入路径。而起点 u 的标记应该放在调用递归之前否则在递归入口处检查cur target时如果起点就是终点你会在没有标记起点的情况下直接走统计流程虽然多数题目保证u ! v但养成防御性编程习惯总没错。6.4 当路径总数没有下限时不要急着用统一累加的办法有些题目不是让你统计所有路径而是让你找一条合法路径或判断路径是否存在。这时候如果还用枚举所有路径 统一累加的方式属实是杀鸡用牛刀。判断是否存在路径时DFS 到终点就可以return true不用继续枚举统计最短路径长度时DFS 并不擅长要换 BFS。我之前写过一篇笔记专门对比 DFS 和 BFS 的适用场景核心就是一句话BFS 适合最短类问题DFS 适合所有/存在性/路径形态类问题。危险系数恰好属于所有这一类这也是它用 DFS 的根本原因。6.5 记录路径的容器选择vector 比 stack 好用很多人一开始用stackint存当前路径但回溯时 stack 不方便遍历——你没法方便地输出或统计整条路径里所有节点。vector既能当栈用尾端 push/pop又能随时遍历是回溯题的最佳容器。等你以后做输出所有路径的题时你会更加感激 vector 这个选择。6.6 剪枝是否有必要在危险系数这道题里剪枝空间不大因为所有简单路径都是有效路径不存在当前路径已经不可能到达终点的明显剪枝条件。但有一个可以做的优化如果当前节点除了通向终点的方向外还连接着大量子图可以提前判断这些子图是否与终点连通。不过这个优化需要对每个节点预先跑可达性判断复杂度反而可能增加得不偿失。所以练习阶段我建议先把暴力枚举写对、写稳再考虑优化——毕竟练习的目标是理解 DFS 的工作机制。7. 其他语言实现的差异点Python 和 Java 的注意细节如果你用 Python 写这题要注意递归深度。默认递归深度只有 1000 左右而 N 可能到 1000DFS 从 u 走到 v 的路径长度如果超过递归深度直接 RecursionError。解决办法是手动设置递归上限import sys sys.setrecursionlimit(1000000)然后 Python 的 DFS 写法要注意把全局变量放到列表里通过nonlocal或者在函数外定义。我以前写 Python 版的时候直接在函数里计数totalPaths结果每次递归都把它当成局部变量初始化直接报 UnboundLocalError。修正方式是在统计变量外层用[0]这种列表包装或者明确声明nonlocal。Java 的话用类成员变量比较省心但要注意递归调用栈默认大小在小数据量下没问题如果递归太深也可能栈溢出这时可以声明一个Deque来模拟栈不过实现复杂度会高出不少。练习阶段建议还是用递归因为可读性好数据范围也扛得住。下面是我当时写的 Python 版本核心部分你可以对照着看import sys sys.setrecursionlimit(1000000) def solve(): n, m map(int, input().split()) adj [[] for _ in range(n 1)] for _ in range(m): a, b map(int, input().split()) adj[a].append(b) adj[b].append(a) u, v map(int, input().split()) visited [False] * (n 1) path [] cnt [0] * (n 1) total_paths 0 def dfs(cur): nonlocal total_paths if cur v: total_paths 1 for node in path: cnt[node] 1 return for nxt in adj[cur]: if not visited[nxt]: visited[nxt] True path.append(nxt) dfs(nxt) path.pop() visited[nxt] False visited[u] True path.append(u) dfs(u) if total_paths 0: print(0) return danger 0 for i in range(1, n 1): if i u or i v: continue if cnt[i] total_paths: danger 1 print(danger) if __name__ __main__: solve()Python 版的性能肯定不如 C但逻辑完全一致。如果数据量大记得把sys.stdin换成buffer读取方式加快输入或者干脆用 C 写。8. 实战验证我用一个具体图测试的完整过程为了确认代码逻辑没毛病我构造了一个小图手动验证。图结构如下无向6 7 1 2 1 3 2 4 3 4 4 5 5 6 4 6 u 1, v 6画出来大概是1 连着 2 和 32 和 3 都连着 44 连着 5 和 65 也连着 6。从 1 到 6 的路径有1 - 2 - 4 - 5 - 61 - 2 - 4 - 61 - 3 - 4 - 5 - 61 - 3 - 4 - 6一共 4 条。逐条统计节点 2 出现在路径 1 和 2 中共 2 次不等于 4。节点 3 出现在路径 3 和 4 中共 2 次不等于 4。节点 4 出现在全部 4 条路径中等于 4危险。节点 5 出现在路径 1 和 3 中共 2 次不等于 4。所以危险系数 1只有节点 4 是必经节点。我代码跑出来的结果也正是 1。这里有一个很有意思的点4 这个节点在这个图里确实是把整个图劈成两半的咽喉删掉 4 之后1 所在的左半边和 6 所在的右半边完全断开。而 2 和 3 虽然也是某种意义上的分支节点但它们都可以被绕过——从 1 到 6 既可以走 2 也可以走 3所以不是危险节点。这个验证案例强烈说明危险系数不等于割点数量它比全局割点更精细。我之后又测试了一个不存在路径的图3 1 1 2 u 1, v 3显然 1 和 3 不连通totalPaths 0输出 0。如果不加totalPaths 0判断结果会是 1错误。这里也验证了我前面强调的那个坑。9. 如果你想把题目改难哪些变体值得挑战练习做完不是终点我习惯把题目做几个变形来检验自己是否真懂。危险系数这个题你可以尝试以下变体输出具体的危险节点编号只需在统计时把满足条件的节点收集起来排个序输出。求任意两条路径的交集节点本质就是所有路径的公共节点和危险系数等价但表述绕了一点。图带权值求所有路径中某节点的出现次数加权和DFS 时可以给每条路径一个权重累计时乘上权重即可。有向图版本的危险系数这个改动会让问题更有意思。有向图中从 u 到 v 的路径必须沿着边的方向走DFS 时只遍历出边即可。但要注意有向图的必经节点判定还依赖于图的强连通结构暴力枚举路径依然是可行的只是路径方向有了限制。把 u 和 v 变成一对多给定一个源点 u 和若干目标点集合求所有从 u 到任一目标点的路径公共节点。这个变体可以锻炼你合并多条路径统计的能力。我最推荐第 4 个因为它迫使你从无向图的对称思维跳出来重新思考 DFS 的遍历顺序。我在这道题的练习笔记里写过一句话无向图DFS让你觉得图很友好有向图DFS才真正考验你对方向感的把握。10. 一点个人练习建议别急着看题解先自己憋一遍最后说点我个人做题的习惯可能对正在刷 DFS 练习的人有帮助。危险系数这道题我第一次做其实没看题解就是自己画图、推条件、写代码然后被统计条件错误坑了一下午。但现在回头想那一下午的试错比看十篇题解都有用。因为只要你亲手经历过枚举所有路径时访问标记不同步导致路径漏统计的诡异现象以后再遇到套着各种外衣的回溯题你一眼就能认出问题的本质DFS 回溯的本质是搜索树上的栈帧管理任何状态都必须随递归进入而建立、随递归退出而销毁。另外做题时我建议你准备一张纸一支笔。每写一个 DFS先在纸上画一个 4 节点的小图手动模拟一遍递归树的展开过程把你期望的输出写下来再让程序跑。如果每道题都能这样练你的 Debug 能力会提升非常快。别觉得这麻烦很多看似玄学的 Bug其实只要把递归过程在纸上展开一遍就豁然开朗了。还有一点不要因为 DFS 代码看起来短就觉得自己掌握了。危险系数这道题真正教会我的是——代码只有十几行但如何设计统计条件和回溯时机才是算法的灵魂。你把这些灵魂层面的东西想明白了哪怕面试或者比赛里遇到一道全新的回溯题你也能迅速进入状态。