从AtCoder 226 C题学反向DFS：依赖遍历的思维转变

刚开始刷 AtCoder Beginner Contest 的题单时看到 226 的 C 题 “Martial artist”我的第一反应是这又是一个披着故事外衣的图论题。等真正读完题发现它比我预想的还要典型——它考察的不是什么冷门算法而是“能不能从终点反向思考”这个最朴实却又最容易在赛场上被忽略的能力。这道题的定位很有意思说难吧它连最短路径都没考说简单吧每次 ABC 的 C 题都有一批人卡住主要不是卡在代码实现而是卡在“正着想的惯性”上。我身边就有朋友赛后看题解拍大腿“这不就是反向 DFS 吗”但也正是这种题最能拉开选手之间思维习惯的差距。这篇文章不打算只丢一个 AC 代码我想把读题、踩坑、换思路、写实现这条完整链路都拆开讲一遍尤其是那些“题目里没写但你必须知道”的细节。1. 题目到底在考什么先别急着写代码1.1 把故事翻译成图论语言Martial artist 的题目背景大概是这样的你扮演一个武者想要学会编号为 N 的招式。每个招式 i 都有对应的学习时间 T_i并且想要学习招式 i必须先掌握若干前置招式 A_i1, A_i2, ..., A_iK_i。也就是说这些招式之间存在先后依赖关系。题目问从完全不会任何招式的状态开始至少需要花多少总时间才能学会 N 号招式把故事扒掉剩下的模型非常干净有 N 个节点代表 N 个招式对每个招式 i它依赖的前置招式可以看成一条从 A_ij 指向 i 的有向边你要计算的是为了学会目标节点 N它的“依赖闭包”里所有节点的学习时间之和。这里有个特别容易误解的点题目问的是“最少总时间”很多人会下意识以为是求 N 号节点到某个起点的最短路径或者需要做拓扑排序之类的操作。其实完全不是。每个招式只需要学一次而且前置关系不会因为学习顺序的改变而节省时间所以答案就是目标节点依赖集合内所有 T_i 的总和。它不是路径问题也不是最优化问题而是一个“集合遍历”的问题。题目给了一个关键保证输入保证一定存在某种学习顺序也就是说依赖关系构成一个有向无环图DAG不存在循环依赖。这一点非常重要因为它决定了你可以放心地做遍历不用担心死循环或“先有鸡还是先有蛋”的困境。1.2 约束条件里的信息量再来看数据范围。这道题 N 的上限是 2×10^5每个招式的学习时间 T_i 最大可以到 10^9K_i 的总和也在 10^5 量级。这三个数字放在一起基本就是在明示几件事不可以使用 O(N^2) 的算法必须线性或近似线性答案必须用 64 位整数保存int 最多只能存到约 2.1×10^9而最坏情况下答案可能达到 2×10^14稳稳爆掉 int存储所有前置关系是允许的vector 嵌套没有问题一次性读入处理即可。这些约束在题目里是客观存在的做题时一定先扫一眼。很多人不是不会写解法而是没注意 long long白送一个 WA这种错误在赛场上最亏。2. 我一开始为什么写错了正向 BFS 的两个坑2.1 坑一重复累加前置招式的时间我第一次做这道题时脑子里冒出的想法是那就从 1 号招式开始正向 BFS 吧遇到 N 就停止过程中把所有经过的招式时间累加。听起来很顺但仔细一推就发现问题同一个招式可能被多条依赖路径同时需要。举个最简单的例子招式 A 需要 2 点时间它没有前置招式 B 需要 1 点时间前置是 A招式 C 需要 1 点时间前置是 A招式 N 需要 1 点时间前置是 B 和 C。真正学会 N 需要哪些招式A、B、C、N各学一次总时间是 2 1 1 1 5 点。但如果正向 BFS 从 1 号开始“顺着走”从 A 出发会走到 B再从 B 走到 N又从 A 出发走到 C再从 C 走到 N。A 这个节点会被访问两次如果你朴素地把访问到的每个节点时间都加到 ans 里A 的时间就被计算了两遍结果变成 6 点或者更多。有同学可能会说那我加个 visited 数组不就行了问题就在这里。如果加 visited 去重正向 BFS 确实能解决重复累加的问题但你会立刻撞上第二个坑。2.2 坑二学了用不到的招式正向 BFS 的另一个麻烦是你并不知道哪些节点最终能通向 N。如果你从所有节点出发盲目遍历或者从 1 号开始一路往后扫很可能把根本不在 N 的依赖链上的招式也加进答案里。考虑这样一个场景N 5但 1 号招式是一个完全孤立的支线它只通向 2 号而 2 号既不是 5 的前置也不影响 5 的学习。正向 BFS 如果从 1 开始就会把 1 和 2 的时间也累加进去最后答案偏大。所以你必须在遍历过程中判断“这个节点是否最终能到达 N”这通常意味着你要么做一次反向可达性标记要么建反图再跑一次某个遍历写起来越来越绕。本质上正向思路的难点在于你不知道哪些节点是“有用的”。而反向思路完全绕开了这个问题——从 N 出发只关心那些真正被 N 依赖的节点天然不会混入无关招式。我后来复盘时意识到这题的考点其实不是“会不会 BFS/DFS”而是“能否意识到正反两个方向的计算复杂度天差地别”。正向想做到不重不漏需要先确定可达集合再做累加反向一次遍历就同时完成“筛选”和“求和”。这种方向上的选择才是竞赛题真正想训练的东西。3. 正确解法从目标招式反向遍历依赖闭包3.1 反向遍历的直觉像查家谱如果你要准备一场家庭聚会需要通知所有长辈但你不知道家族谱系全貌只知道“要请某个人就必须先请他的父母”。这时候你会不会从名单上的人开始逐个问“他们的父母是谁”然后把父母加进名单这就是反向遍历的直觉。放到这道题里也一样先把 N 号招式加入“必学名单”看 N 的前置招式有哪些把它们加入名单再看这些前置招式各自的前置招式继续加入名单重复这个过程直到名单不再变大。每个招式只会被处理一次用 visited 数组保证不重复。“必学名单”里所有招式的时间总和就是答案。这个过程本质上是在有向无环图上从目标节点出发沿反方向访问它的所有祖先节点。这里有一个特别舒服的地方题目输入已经天然给了你“反向邻接表”。因为输入数据对每个招式 i 都存储了它的前置列表而从节点 i 出发反向走要访问的邻居恰恰就是这些前置招式 A_i1...A_iK_i。也就是说你根本不需要额外建一张反图直接用原始前置列表就能完成反向遍历。这一点当时让我觉得这个题设计得很巧妙——数据和算法方向刚好是吻合的。3.2 迭代 DFS 的完整推导用伪代码描述一下核心流程ans 0 visited 全 false stack [N] while stack 非空: u stack.pop() if visited[u]: continue visited[u] true ans T[u] for 每个前置招式 v in 前置列表[u]: if not visited[v]: stack.push(v) 输出 ans为什么这个流程正确因为它只做了一件事找到 N 的所有祖先节点并去重。N 的祖先节点集合恰好就是必须学习的招式集合。由于题目保证依赖关系是 DAG这个遍历一定能终止visited 数组又保证了每个节点最多入栈一次、出栈一次所以不会指数爆炸。关于入栈时机我想多说一句。常见的写法有两种一种是“在 pop 时检查 visited 并累加”另一种是“在 push 前就检查 visited”。两种都能 AC但前者更稳妥。因为如果只靠 push 前检查你无法保证同一个节点不会被重复 push 多次——比如节点 x 同时是两个已访问节点的前置它在第一次被某个节点 push 时未访问入栈但在被另一个节点 push 时它还没被 popvisited 仍然是 false于是又被 push 了一次。虽然答案不会重复算因为 pop 时有 visited 检查但栈里会积压一些没用的节点数据大时浪费内存。我习惯的写法是 push 前检查 visitedpop 时再检查一次双保险栈大小和每个节点的入栈次数都得到控制。4. 两种落地实现递归 DFS 与显式栈4.1 递归写法与递归深度隐患很多第一次接触这道题的人最喜欢写递归 DFS因为代码最短#include bits/stdc.h using namespace std; vectorlong long t; vectorvectorint pre; vectorint vis; long long ans 0; void dfs(int u) { if (vis[u]) return; vis[u] 1; ans t[u]; for (int v : pre[u]) dfs(v); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; t.assign(N 1, 0); pre.assign(N 1, {}); vis.assign(N 1, 0); for (int i 1; i N; i) { int k; cin t[i] k; pre[i].resize(k); for (int j 0; j k; j) cin pre[i][j]; } dfs(N); cout ans \n; return 0; }这个写法在样例和小数据下完全没问题但你得留个心眼递归深度可能非常深。如果依赖链是一条直线比如 1 → 2 → 3 → ... → N那么从 N 开始递归会一路倒着访问到 1深度为 N 的量级。N 最大 2×10^5在 C 的默认栈空间下这种深度很容易爆栈。AtCoder 的 Linux 环境默认栈大小通常是 8MB递归一层可能消耗几十字节到上百字节2×10^5 层确实存在风险。所以我的建议是除非你确认测试数据里依赖链不会很长否则不要用递归交这道题。就算能过也不是一个稳健的做题习惯。竞赛里因为递归爆栈导致的 RE赛后看代码才发现“算法没错但栈炸了”这种体验真的很冤枉。4.2 显式栈写法为什么它更稳显式栈写法把递归调用改成自己维护一个 vector 当栈彻底绕开系统栈深度限制。逻辑完全一致代码量也就多两行#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin N; vectorlong long t(N 1); vectorvectorint pre(N 1); for (int i 1; i N; i) { int k; cin t[i] k; pre[i].resize(k); for (int j 0; j k; j) cin pre[i][j]; } vectorchar visited(N 1, 0); vectorint stk; stk.push_back(N); long long ans 0; while (!stk.empty()) { int u stk.back(); stk.pop_back(); if (visited[u]) continue; visited[u] 1; ans t[u]; for (int v : pre[u]) { if (!visited[v]) { stk.push_back(v); } } } cout ans \n; return 0; }这里有个值得说的细节vector 比 vector 更适合做 visited 标记。vector 在 C 里是出了名的特化容器它做了位压缩读写行为跟普通数组不太一样在某些场景下会带来意外性能损失而且不能直接取引用。我见过有人在比赛里用 vector 然后奇怪自己为什么 TLE虽然不是这个题但习惯上我直接用 vector 就省心了。显式栈还有一个好处方便你随时加日志调试。比如你想看每个节点是谁被谁触发的只要在入栈前打印一行就行递归版就没这么好插桩。比赛中这种“可调试性”其实很值钱尤其在样例都过了但交上去 WA 的时候。4.3 Python 实现读入提速与递归限制Python 版本也完全可以做但要注意两个东西一是输入量不小建议一次性读入二是递归深度限制。先看代码import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) it iter(data) n next(it) t [0] * (n 1) pre [[] for _ in range(n 1)] for i in range(1, n 1): t[i] next(it) k next(it) arr [next(it) for _ in range(k)] pre[i] arr visited [False] * (n 1) stack [n] ans 0 while stack: u stack.pop() if visited[u]: continue visited[u] True ans t[u] for v in pre[u]: if not visited[v]: stack.append(v) print(ans) if __name__ __main__: main()用 sys.stdin.buffer.read().split() 一次性读入并转成 list比反复调用 input() 快很多。Python 的解法和 C 在数据结构上几乎一一对应只是要注意栈用 list 模拟即可。如果你非要用递归写法至少加上 sys.setrecursionlimit(10**7)但即便设置了递归深度Python 的递归调用开销也比迭代大得多在极限数据下容易慢。所以我始终建议用显式栈版本这跟语言无关是一种更通用的工程习惯。5. 复杂度、边界条件与实测数据5.1 为什么复杂度是 O(N ΣK)很多人知道这题是线性但不一定说清楚为什么。反向遍历的每个关键操作消耗在哪里让我拆开看visited 数组保证每个节点最多被“成功处理”一次处理时执行一次 ans t[u]这是 O(N) 的每个节点的前置列表在它被处理时会被完整扫描一遍所有节点的前置列表总长度是 ΣK因此这部分总代价是 O(ΣK)显式栈的 push/pop 次数与节点入栈次数成正比而每个节点最多在 visited 仍为 false 时被 push 一次所以栈操作也是 O(N) 级别。合在一起时间复杂度就是 O(N ΣK)空间复杂度是 O(N ΣK)用来存 t、pre 和 visited。这个复杂度对于 N2×10^5 绰绰有余即使在 Python 下跑实测通常也不到 0.5 秒。所以这道题的时间瓶颈完全不在算法而在于你想清楚方向的那几秒钟。5.2 三个容易栽的边界条件这类题 WA 的原因往往很集中在几个小地方我列一下自己踩过的坑目标招式本身也要算时间。你从 N 开始遍历第一次 pop 出 N 时就要累加 t[N]而不是从它的前置开始算。很多人初始化 ans 为 0然后遍历前置最后忘了加自己样例如果恰好有反例会暴露但万一样例太水就很容易漏。答案必须用 long long。这个前面已经提过最坏情况每个招式都要学每个招式耗时 10^9N2×10^5总和是 2×10^14int 装不下。C 里用 long longPython 不需要担心这个但如果你用其他静态类型语言一定要记得选 64 位整数。没有前置招式的节点要正确处理。输入中 k0 的招式就是依赖链的“叶子”反向遍历到它时它的 pre 列表为空不会继续入栈流程自然结束。不要在这种节点上做特殊判断也不需要额外构造“虚拟根节点”。还有一个容易被忽略的输入索引从 1 开始。如果你习惯用 0-based 的数组一定要在分配 vector 时留出 N1 个位置否则访问越界可能产生难以排查的运行时错误。5.3 造几组数据验证算法为了方便你本地自测我造了几组数据对照着看更容易理解反向遍历的执行过程。样例 1最简单的依赖链3 2 0 4 0 1 2 1 2解释招式 3 需要先学 1 和 2招式 1 耗时 2招式 2 耗时 4招式 3 耗时 1。答案 2 4 1 7。从 3 出发反向遍历依次访问 1 和 2各累加一次正确。样例 2同一前置被多处依赖5 5 0 3 1 1 4 1 1 2 1 2 1 2 3 4解释招式 2 依赖 1招式 3 依赖 1招式 4 依赖 3 和 2招式 5 依赖 4。整个依赖闭包是 1, 2, 3, 4, 5总时间 5 3 4 2 1 15。反向遍历时1 会被“访问候选”多次但 visited 保证它只入栈并累加一次这就是去重的价值。样例 3验证 long long 的必要性2 1000000000 0 1000000000 1 1答案显然是 2×10^9刚好超过 int 的上限一点点用 32 位整数就会出问题。这种极端值题目里很可能藏在边界测试里稍微不留神就 WA。6. 从这一题延伸出去的通用思路6.1 反向思维在竞赛题里的三种常见用法Martial artist 这道题最值得提炼的不是反向 DFS 本身而是“反向思维”这个方法论。竞赛里很多题目正着做很难反着做却异常简单。我至少能想到三个常见场景依赖/前置关系遍历像本题一样当问题是“从某个目标出发需要哪些前置”反向遍历依赖图通常比正向搜索简洁得多。典型代表还有课程表问题拓扑排序的前置课程、技能树计算等。并查集离线删边如果题目要求你不断删边并查询连通性正着删很难维护反着来把删边操作倒序看成加边操作用并查集一路合并最后再把答案倒过来输出这就是经典的“反向并查集”套路。最短路径/可达性的多源问题有时候正着跑一次 Dijkstra 不够但如果你从目标点反向建图跑一次就能把“哪些点能到目标”一次性求出来。这些方法论的共同点是善于观察“数据输入方向”和“目标查询方向”是否一致。如果输入结构天然是“从依赖到被依赖”而你要查的却是“从目标回溯依赖”那就别犹豫反着遍历。6.2 如果题目改一改你还能接住吗刷题不能只停留在 AC我习惯再多想几步如果题目稍微变一下我的解法还能不能用如果改成“输出 N 号招式所有必要前置招式的编号集合”那这个算法只需要把 ans t[u] 改成把 u 加入答案集合即可其他完全不变。如果改成“求学会 N 号招式所需的最少时间但每个前置招式可以有多个人同时学习”这听起来像并行调度那就变成完全不同的题目了大概率需要拓扑排序 DP 求关键路径。如果改成“招式依赖之间存在环怎么办”那问题直接不成立了因为环意味着你永远无法开始学习任何一个环内招式。这种时候要判断是否有解就需要拓扑排序找环。如果改成“每个招式可以学多次每次耗时不同求学会 N 的最短时间”那就是最短路问题了可以用 Dijkstra 或 BFS。想清楚这些变式你对这道题的理解就不再只是“背一个反向 DFS”而是真正掌握了一类问题的解题框架。以后再遇到类似的依赖类题目至少第一时间不会走正向 BFS 的弯路。我在实际刷题中还有一个体会每次 AC 之后不要急着看下一题花五分钟在草稿纸上把“为什么我的第一次思路会错”写清楚。这个复盘动作看起来不起眼但积累多了你会发现自己在一道题上犯过的错误真的会在十道题之后帮你避开相似的大坑。Martial artist 对我来说就是这样一个典型的思维转折点希望你也能从这题里拿走点什么不只是那一个 AC。