AtCoder ABC226 C题：反向DFS解武术技能依赖问题

Contest 226 - C - Martial artist，这道题出自 AtCoder Beginner Contest 226，是那次比赛里第三题。题面讲一位叫 Takahashi 的武术家要学招式，每个招式有学习时长，还可能有前置招式，想学某个招式前必须先把它的前置招式全部学会。目标很简单：学会第 N 个招式最少要花多少分钟。但真正动手之后你会发现，这题披着模拟题的外衣，内核却是一道图论题——而且从哪个方向搜，决定了你的代码是干净利落还是又臭又长。这篇博文把从读题到 AC 的完整过程记录下来，适合准备 ABC 入门、或者刚接触 DFS/BFS 基础图的选手参考，我会把每一步选择背后的原因也一并讲清楚。

1. 先读懂题：武术家到底在练什么

1.1 题面还原与核心规则

原题的描述很简单：Takahashi 是一名武术家，他想学会编号从 1 到 N 的招式。第 i 个招式的学习耗时是 T_i 分钟，并且学习它之前必须先学会 K_i 个指定的招式。注意，K_i 可以为 0，也就是这个招式没有任何前置门槛，随时能学。

整个训练过程没有复杂的并发或顺序约束，一个人同一时间只能专注练一个招式。所以结论很直接：如果最终要学的技能集合是 S，那么总耗时就是 S 里所有招式耗时之和。很多人刚开始会被“最少需要多少分钟”这几个字带偏，以为要算最优调度或者并行安排，实际上题目根本没给你并行训练这个设定，老老实实把依赖链上的所有时间加起来就行。

题目的目标是：学会第 N 个招式。注意，不是学会全部招式，也不是学会某个给定集合，而是仅仅最后一个招式。这是整道题最重要的一个限定条件，后面所有思路都围绕它展开。

1.2 数据规模与输入格式

输入格式如下：第一行是 N，接下来 N 行，每行描述一个招式。第 i 行开头是 T_i 和 K_i，如果 K_i 大于 0，后面还跟着 K_i 个整数，表示这个招式需要的前置招式编号。所有编号都是 1-based，也就是从 1 到 N。

数据规模方面，N 最大能到 2×10^5，每个招式的耗时 T_i 可以到 10^9 级别。这个规模意味着不能用 O(N^2) 的暴力，必须在 O(N + 总前置数) 的复杂度内解决。另外题目保证每个招式的前置招式编号一定小于它自身的编号，也就是 A_{i,j} < i。这个性质很关键，它保证了整个依赖图是一个有向无环图，不存在循环依赖。换句话说，按照编号从小到大天然就是一个合法的拓扑顺序。

1.3 这题真正考的是什么

很多人第一眼会认为这题是模拟：从第 N 个招式开始，递归地找前置，把所有需要学的招式标记出来，然后求和。这确实是正确方向。但难点在于，如果你没有建立图论的视角，很容易陷入“正向遍历所有技能，判断哪些被需要”的坑里。

这题真正想考察的是：从目标节点出发，在一个有向图中做“反向可达性搜索”。你需要的不是整个图的信息，而是目标节点 N 的依赖闭包。在图里，依赖关系是边，前置技能是前驱节点，从 N 出发沿着“前置关系”反向走，能走到的所有节点就是必须学的招式，再把这些招式的时间加总就是答案。

2. 思路选型：为什么反向 DFS 才是这题的钥匙

2.1 正向拓扑排序的“过度设计”

我先说说我一开始的错误思路，这个坑很有代表性。看到“技能依赖前置技能”，第一反应就是拓扑排序：把所有招式按依赖关系排好序，然后顺着拓扑序从前往后累加时间，最后输出第 N 个招式的时间。听起来很合理，但仔细一算就发现问题了。

拓扑排序会处理所有 N 个技能，但题目只要第 N 个技能的依赖信息。如果 N 的依赖链很短，或者很多技能与第 N 个招式完全没有关系，那这些无关技能的计算完全是白费。更麻烦的是，单纯顺着拓扑序累加还有重复计算问题：两个不同招式可能依赖同一个公共前置招式，如果简单地把每个技能的前置时间累加，这个公共前置会被重复计数，答案就会偏大。

这不是说拓扑排序不能做，它需要额外处理去重逻辑，代码会明显变长。对一个 ABC 的 C 题来说，明显有更轻量、更贴合的解法。

2.2 反向思考的关键一步

正确做法是反过来：从第 N 个招式出发，沿着“前置招式”这条边往回走。每走到一个招式，就把它标记为“需要学”，然后把它的耗时加入答案。由于题目保证前置招式的编号一定小于当前招式，所以反向走的时候编号始终在递减，不存在环，也不会走入“不需要学”的分支。

这个思路的本质，是只探索“必要节点”。从 N 出发能到达的每一个点，都是学会 N 所绕不开的技能；从 N 出发到不了的技能，不管它多复杂、依赖多深，都和第 N 个招式无关，直接忽略。也就是说，你不需要关心全图的整体结构，只关心目标节点 N 能反向触达的那一小块。

我习惯用一个生活类比：你要做一道复杂的菜，只需要找出这道菜需要的所有食材和半成品，然后去采购。你不会把整个超市的所有货架都逛一遍，也不会把所有东西都买回家。反向 DFS 就是“按需寻源”，而拓扑排序是“把超市全部盘点一遍再决定买什么”。

2.3 复杂度分析与选型结论

反向 DFS / BFS 的复杂度非常干净：每个节点最多被访问一次，每条依赖边最多被检查一次。假设总前置数为 M，则时间复杂度是 O(N + M) 中的实际访问量，最多也就 O(N + M)，空间复杂度 O(N + M) 用来存依赖边和访问标记。

在 N 最大 2×10^5 的约束下，这个复杂度完全够用，Python 也能轻松跑进时间限制。而如果选择拓扑排序，虽然复杂度同样是 O(N + M)，但常数更大，逻辑更绕，还容易在去重上翻车。所以结论很明确：这题的正解就是反向搜索，DFS 或者 BFS 都行，核心思想一致，区别只在实现细节。

顺便说一句，为什么很多题解推荐 DFS 而不是 BFS？因为这里没有求最短路径的需求，DFS 实现起来更短，用一个递归函数加一个访问标记就完成了。但考虑到递归深度的问题，用迭代栈写 DFS 或者直接用队列写 BFS 也完全没有问题。我下面给出的代码里，迭代栈版本是我个人最推荐的——既保持了 DFS 的简洁语义，又避免了递归爆栈的隐患。

3. 完整代码实现与逐行拆解

3.1 Python 递归版

先看递归版，这是最直观的写法。先读入数据，把每个招式的耗时存到 cost 数组，把前置依赖存到 need 列表，下标统一从 0 开始。然后从第 N-1 个招式（也就是输入中的第 N 个）开始 DFS。

import sys sys.setrecursionlimit(1 << 20) input = sys.stdin.readline n = int(input()) cost = [0] * n need = [[] for _ in range(n)] for i in range(n): row = list(map(int, input().split())) cost[i] = row[0] k = row[1] for j in range(k): need[i].append(row[2 + j] - 1) vis = [False] * n def dfs(u): if vis[u]: return 0 vis[u] = True total = cost[u] for v in need[u]: total += dfs(v) return total print(dfs(n - 1))

这里最关键的是 dfs 函数里的if vis[u]: return 0。它保证了同一个技能即使被多个前置技能依赖，也只会被累加一次。如果你把这一行去掉，公共前置会被反复计入答案，结果一定偏大。这个函数的设计思路是：“如果这个技能已经被访问过，说明它的耗时已经算进答案了，本次调用不应该产生任何新增贡献，直接返回 0”。

3.2 Python 迭代栈版（推荐）

递归版的隐患在于 Python 默认递归深度只有大约 1000 层，虽然题目依赖链最长不会超过 N，但 N 有 2×10^5，一旦出题人构造一条长链，递归版就会在运行时报 RecursionError。设置sys.setrecursionlimit(1 << 20)能缓解，但有些在线评测环境对递归栈本身有限制，用迭代栈一劳永逸。

import sys input = sys.stdin.readline def main(): n = int(input()) cost = [0] * n need = [[] for _ in range(n)] for i in range(n): row = list(map(int, input().split())) cost[i] = row[0] k = row[1] if k: need[i] = [x - 1 for x in row[2:2 + k]] vis = [False] * n stack = [n - 1] vis[n - 1] = True ans = 0 while stack: u = stack.pop() ans += cost[u] for v in need[u]: if not vis[v]: vis[v] = True stack.append(v) print(ans) if __name__ == "__main__": main()

注意这里我把vis[n - 1] = True放在入栈之前，避免重复入栈。每次从栈里弹出一个节点，先加它的耗时，再把它所有未被访问的前置技能压入栈中。由于题目保证依赖编号一定小于自身，栈内元素不会出现环，整体逻辑非常稳定。

3.3 C++ 参考实现

如果你习惯用 C++ 参赛，参考实现如下。核心逻辑和 Python 迭代版一致，唯一的区别是使用了long long来存答案，防止累加时溢出。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<long long> cost(n); vector<vector<int>> need(n); for (int i = 0; i < n; i++) { int k; cin >> cost[i] >> k; need[i].resize(k); for (int j = 0; j < k; j++) { cin >> need[i][j]; need[i][j]--; } } vector<bool> vis(n, false); stack<int> st; st.push(n - 1); vis[n - 1] = true; long long ans = 0; while (!st.empty()) { int u = st.top(); st.pop(); ans += cost[u]; for (int v : need[u]) { if (!vis[v]) { vis[v] = true; st.push(v); } } } cout << ans << '\n'; return 0; }

在实际比赛中，C++ 的vector<vector<int>>用来存前置边就够了。如果你担心内存碎片，也可以用邻接表的数组形式，但选手赛里vector的写法在 2×10^5 规模下完全扛得住，不需要额外优化。

4. 手动跑一遍流程：从样例到边界数据

4.1 用官方样例完整走一遍

官方给的样例输入是：

3 3 0 4 1 1 2 2 1 2

意思是：技能 1 耗时 3，无前置；技能 2 耗时 4，需要先学技能 1；技能 3 耗时 2，需要先学技能 1 和 2。目标是学会技能 3。

用迭代栈模拟一遍：

• 初始化stack = [2]，表示 0-based 下的技能 3，vis[2] = true，ans = 0。
• 弹出 2，ans += cost[2]等于 2。遍历 need[2] 得到前置 [0, 1]。
  • 技能 0 未访问，标记后入栈。
  • 技能 1 未访问，标记后入栈。
• 弹出 1，ans += cost[1]等于 6。遍历 need[1] 得到前置 [0]，但技能 0 已经被访问过，跳过。
• 弹出 0，ans += cost[0]等于 9。技能 0 无前置，直接结束。
• 输出 9。

注意一个细节：技能 1 同时是技能 2 和技能 3 的前置，但它在被弹出只是累加了一次。如果去掉 vis 数组，技能 1 会被两个分支各访问一次，答案就会变成 2 + 4 + 3 + 3 = 12，明显错误。

4.2 一个专门用于观察重复依赖的样例

再构造一个更极端的例子来展示 vis 标记的作用：

4 10 0 5 1 1 5 1 1 1 2 2 3

输入解读：技能 1 耗时 10，无前置；技能 2 耗时 5，需要学技能 1；技能 3 耗时 5，需要学技能 1；技能 4 耗时 1，需要学技能 2 和 3。

目标技能 4 的依赖链里，技能 1 被技能 2 和 3 同时依赖。正确结果应该是 1 + 5 + 5 + 10 = 21，因为技能 1 只需要学一次。用迭代栈模拟：

• stack = [3]，ans = 0。
• 弹出 3，ans += 1，前置是 [1, 2]，入栈。
• 弹出 2，ans += 5，前置是 [0]，入栈。
• 弹出 1，ans += 5，前置是 [0]，但技能 0 已被访问，跳过。
• 弹出 0，ans += 10，结束。

答案 21，正确。这个例子如果交给递归版但没有 vis 保护，结果就是 1 + 5 + 10 + 5 + 10 = 31，差了正好一个 10——这就是公共前置被重复计数的标准症状。以后你在比赛里发现答案莫名偏大，基本就是少了这个去重标记。

4.3 如何快速验证你的代码

写完后不要急着提交，先自己构造几组边界数据。第一组：N=1，只有一行10 0，输出应为 10，因为没有前置，学会第 1 个招式就是它的耗时本身。第二组：长链依赖，例如 N=4，技能 2 依赖 1，技能 3 依赖 2，技能 4 依赖 3，每个耗时都是 1，答案是 4。第三组：全部没有前置，答案是 T_N 本身。这几组数据覆盖了“单节点”“长依赖链”“无依赖”三种情况，能帮你把大多数低级错误提前拦下来。

5. 常见问题与排错速查

5.1 答案偏大，找了半天没发现问题

这是最典型的 Bug：忘了去重。症状是输出总是比预期答案大，而且大出的部分刚好是某个公共前置的耗时。原因就是递归/搜索时没有加 visited 判断，同一技能被不同分支重复累加。如果你用的是递归写法，检查 dfs 函数开头是否写了if vis[u]: return 0；如果用 BFS 或迭代栈，检查入栈前是否判断了not vis[v]。

5.2 递归爆栈 RecursionError

Python 默认递归深度大约 1000，在长依赖链下必炸。解决办法有两个：一是在递归版开头加sys.setrecursionlimit(1 << 20)，但这只是调高上限，极端情况下依然可能受操作系统栈限制；二是直接换迭代栈版，完全避免递归调用。我个人倾向后者，尤其在大规模数据下更省心。

5.3 下标没从 1 转 0，答案错得离谱

AtCoder 输入是 1-based，而 Python 数组下标是 0-based。读入前置技能编号时一定要减 1。如果你忘了减 1，need里存的编号整体偏大 1，访问时可能越界；更隐蔽的是，Python 列表的负索引会让arr[-1]悄悄访问最后一个元素，代码不报错但结果完全错误。建议读入后立刻处理，并且用一个简单的样例验证第一行的技能 1 是否对应数组下标 0。

5.4 C++ 用 int 存答案导致溢出

T_i 最大可以到 10^9，N 最大 2×10^5，理论答案上限会达到 2×10^14，这远远超过了 32 位 int 的范围。如果你用 C++，答案和 cost 数组务必声明为long long。Python 的 int 没有这个顾虑，但也别写成//之类不小心截断的逻辑。

5.5 常见问题速查表

5.6 一个容易被忽略的小细节

题目保证前置招式编号小于自身，所以从 N 反向搜索时不可能出现环。但如果哪天你遇到类似的题，出题人没有给这个保证，你就需要额外考虑环的情况。一般的做法是：要么先用拓扑排序判环，要么在 DFS 时记录“当前递归栈内”的节点，发现重复就说明有环。本题不需要，但养成这个意识，遇到变种题时不至于慌。

6. 题目之外的通用套路：依赖类问题怎么想

6.1 “目标单一，依赖复杂”先想按需搜索

这题的价值不只在 AC 本身，更在于一种解题取向。很多题目的描述都有一个“全局结构”：N 个技能、若干依赖关系、一堆约束条件。如果题目问的是“全局最优”或者“所有节点都需要”,那往往要全量遍历或做全局分析；但如果问的是“只关心某一个特定节点/目标”，那么“按需搜索”往往是最高效、最简单的方式。

这类题目的信号词很典型：给定一个有向无环图，每个节点有代价，节点之间有前置依赖，询问到达某个目标节点最少需要多少总代价。一旦识别出这个模式，直接反向 DFS/BFS，从目标节点出发收集依赖闭包，就八九不离十了。

6.2 vis 标记与记忆化搜索的关系

有读者可能会问：这题能不能用记忆化搜索？本质上是能的。如果你定义一个solve(u)表示“学会技能 u 所需的新增时间”，那么solve(u) = cost[u] + sum(solve(v) for v in need[u])，但要加一个条件：如果 u 已经被处理过，solve(u)返回 0。这其实就是记忆化的变体，只不过这里的“记忆”不是缓存子问题的结果，而是缓存“该节点是否已经被收入答案”。

其实更好理解的方式是：你不需要保存每个子问题的完整返回结果，只需要一个布尔数组记录访问状态。访问过就跳过，这比传统记忆化搜索还要轻量。实际编码时，我建议直接做 vis 标记，不要把它包装成记忆化递归，后者容易让你在“返回什么值”上绕晕。

6.3 后续练习方向

如果你刚做透这一题，想趁热打铁巩固，可以从这几个方向延伸。第一，做几道“反向建图”的题，比如需要从多个终点反向搜索的题目，你会慢慢体会到反向思维在图上有多常用。第二，练习 BFS 和 DFS 两种写法互换，同一个题用队列写一遍、用栈写一遍、用递归写一遍，弄清楚每种写法的注意点。第三，尝试给这题加一些变式，比如求“学会第 N 个招式的最少天数”，如果允许每天并行学多个招式，解法又会变成按层级统计……从一道题延伸出多种问法，是提升图论感觉很有效的方式。

我个人的体会是，这题我第一次做的时候用的是拓扑排序全量处理，代码写了六十多行，还纠结去重逻辑；后来第二次遇到类似题，直接反向栈遍历，二十行不到就写完了。自那以后，但凡看到“求某个目标节点的依赖信息”，我都会下意识地先从终点倒着搜一遍——这个习惯让我在不少比赛里省下了大量时间。希望这篇记录也能帮你把这道经典 C 题一次吃透。