最近把牛客的每日一题捡起来刷，顺手把进度挪进自己的 tracker 里，从双指针刷到图论，碰上了一道很有意思的题：食物链计数。题面不长，数据范围也不吓人，但真写起来，方向、模数、边界条件全踩了一遍。这篇就以这道题为主角，聊聊图论建模和 DAG 上路径计数的完整思路，也聊聊这类题在 tracker 里到底该怎么记、记什么。想搞懂拓扑排序和 DP 怎么配合的，或者正在刷牛客每日一题卡在这道题上的，都能直接照着下面的思路走。
1. 这道题为什么值得在 tracker 里单开一行
1.1 从一道"小题"能带出的知识密度
食物链计数这个名字听起来像是生物题，其实是个标准的图论题。题目大意是：给你若干种生物和它们之间的捕食关系，统计这个生态系统里一共有多少条完整的食物链。所谓完整，就是从生产者出发，一路沿着捕食关系，走到不再被任何生物捕食的顶级消费者，中间不能断。
单看解法，它就是"DAG 上的路径计数"，一行转移方程就能写明白。但这道题妙就妙在，它把好几个单独的知识点压缩在了一起：怎么把文字题意建模成图、怎么判断生产者消费者、为什么必须是有向无环图、拓扑排序的顺序为什么刚好能拿来算 DP、取模和大数要注意什么。很多刷题的人容易忽视的是，这类"小模型题"恰恰是面试和竞赛里最容易变形的母题，搞懂一道，等于搞懂了一整类。
1.2 在 tracker 里给题目打标签的思路
我习惯在 tracker 里给每道题打两三个标签。食物链计数这题，我标的就是"图论""拓扑排序""DAG路径DP"。标签的作用不是晒进度，而是为了后面复盘。比如半个月后我想复习拓扑排序的动态规划用法，直接按标签筛，能一次性把这几天做的同类型题全拉出来，比翻聊天记录、翻提交列表高效得多。所以这道题虽然 AC 之后看起来轻飘飘的，但它在 tracker 里的价值不小，属于"以后能当模板用"的题。
2. 先把题意翻译成图：食物链就是 DAG 上的路径数
2.1 节点、边、方向，一步都不能错
开始写代码之前，最重要的事情是决定建图方向。以常见题面为例：输入一行两个数 x y，表示 x 被 y 捕食。那我们就建一条有向边 x -> y，能量流向是从猎物指向捕食者。
为什么是这个方向？因为一条食物链的逻辑是连续的"被捕食"关系。草被兔子吃，兔子被狐狸吃，那么上一条链应该是"草 -> 兔子 -> 狐狸"，刚好和边的方向一致。我们要统计的，就是从"不被任何东西吃"的生产者出发，走到"不吃任何东西"的顶级消费者的路径条数。如果把方向建成 y -> x，那路径就变成了捕食者指向猎物，跑出来的答案会完全反掉，小样例可能侥幸能过，一到大数据直接崩。所以动手建图之前，先在注释里把边的方向写清楚，能省掉后面一整轮调试。
2.2 用入度和出度判定生产者、消费者
节点有两种特殊角色需要先找出来：
- 生产者：入度为 0，意思是没有任何生物吃它。注意这里要排除一种特殊情况，如果它入度为 0 同时出度也为 0，那它是一个孤立点，不属于任何食物链，后面单独处理。
- 顶级消费者：出度为 0，意思是它不吃任何别的生物。同样，孤立点也满足出度为 0，但它不该被计入答案。
这里容易混淆的是生物直觉和图的定义。现实中也会有一些生物既吃别的又被别的吃，体现到图上就是入度和出度都不为 0 的中间节点，它们负责把上游的路径数传递到下游。
2.3 孤立点是这道题埋得最深的边界
很多第一次写这题的选手会挂在一个看起来不起眼的地方：如果某个生物既不被任何生物吃，也不吃任何生物，它算不算一条食物链？
按题目定义，不算。食物链必须是一个有向的、从生产者到消费者的通路。一个孤立点没有边，路径长度为 0，自然不能叫食物链。处理方法是：初始化 DP 时，只有"入度为 0 且出度大于 0"的点才把 dp 值设为 1 并入队；孤立点的 dp 保持 0，也不进队列。这一步可以在后面统计答案时自动屏蔽掉孤立点。
2.4 手推一个四节点小例子
为了把模型讲清楚，我用一个最小的例子验证一遍。假设有 4 个节点，关系是：1 被 2 吃，2 被 3 吃，1 被 4 吃，4 被 3 吃。建出来的边就是 1->2、2->3、1->4、4->3，对应的生物关系相当于草、兔子、狐狸加上一条老鼠支线。
各节点的入度、出度如下表：
| 节点 | 入度 | 出度 | 角色 |
|---|---|---|---|
| 1 | 0 | 2 | 生产者，路径起点 |
| 2 | 1 | 1 | 中间节点 |
| 3 | 2 | 0 | 顶级消费者，路径终点 |
| 4 | 1 | 1 | 中间节点 |
肉眼数一下，完整食物链有两条：1->2->3 和 1->4->3。答案应该是 2。这个手动推演非常重要，建议刷题时遇到任何新题都先造一个小样例验证自己的模型理解，别急着写代码。
3. 标准解法：Kahn 拓扑排序 + 路径数累加 DP
3.1 状态设计与无后效性
设 dp[v] 表示从任意一个生产者出发，到达节点 v 的食物链前缀数量。注意前缀这个词，因为一条完整食物链走到 v 时，前面的部分已经是一条合法的路径了。
转移方程非常朴素：
dp[v] = sum(dp[u])，其中 u 是所有能走到 v 的前驱节点。
为什么这个方程成立？因为每条从生产者到 v 的路径，最后一步必然经过某个前驱 u，不同 u 代表的路径集合互不重叠，所以直接相加就能得到总数。这个逻辑成立的前提是图中没有环。有环的话，路径可以无限绕圈，"到达 v 的路径数"就变成无穷大了，DP 也无法终止。
这也解释了为什么题目数据必须是 DAG（有向无环图）：捕食关系在现实里不可能形成" A 吃 B，B 又吃 A"的循环，能量流动本身就是单向的，生物学约束和算法约束在这里刚好一致。理解这一点之后，再看到题面里藏着"食物链"三个字，就应该自动翻译成"这是一道 DAG 上的路径计数题"。
3.2 拓扑序为什么是 DP 的正确顺序
知道了 dp[v] 依赖所有前驱 u，关键问题就来了：按什么顺序算 dp？
答案是拓扑序。Kahn 算法的做法是：先把所有入度为 0 的点入队，然后每次从队头取出一个点 u，处理以 u 为起点的所有边，把入度减到 0 的下游节点 v 入队。这样做的效果是：当一个节点 v 第一次从队列里被取出来时，它的所有前驱都已经处理完了，也就是说 dp[v] 已经累加完毕，之后不会再被修改。
这就是"无后效性"：每个节点的状态只依赖它更上游的节点，不依赖下游。拓扑序恰好保证处理每个节点时，它的依赖项都已经算完。你可以把它理解成盖楼，必须先打地基再砌墙，上游没算完，下游不可能先算出正确答案。
3.3 参考代码（C++）
下面是完整的 C++ 实现，采用 vector 邻接表存图。这份代码可以直接拿去交题，但建议自己敲一遍。
#include <bits/stdc++.h> using namespace std; const int MAXN = 500005; const long long MOD = 80112002LL; // 按题目给定模数修改 int n, m; vector<int> g[MAXN]; int indeg[MAXN], outdeg[MAXN]; long long dp[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; // x 被 y 捕食，建边 x -> y g[x].push_back(y); indeg[y]++; outdeg[x]++; } queue<int> q; for (int i = 1; i <= n; i++) { if (indeg[i] == 0 && outdeg[i] > 0) { // 真正的生产者 dp[i] = 1; q.push(i); } // 孤立点：入度出度都为0，dp保持0，不入队 } while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { dp[v] = (dp[v] + dp[u]) % MOD; indeg[v]--; if (indeg[v] == 0) { q.push(v); } } } long long ans = 0; for (int i = 1; i <= n; i++) { if (outdeg[i] == 0) { ans = (ans + dp[i]) % MOD; } } cout << ans << '\n'; return 0; }几个值得注意的细节：
- 初始化时只让生产者（入度 0、出度大于 0）入队并赋 dp 初值 1。孤立点 dp 保持 0，最后统计答案时它的贡献自然就是 0。
- dp 在转移时取模。这里用了 long long 而不是 int，原因是相加后再取模的过程中，如果模数是 1e9+7 级别的数，两个不超过模数的 dp 值相加会接近 2e9，已经摸到 int 上线的边沿，用 long long 彻底规避风险。
- 最后统计答案是累加"出度为 0"节点的 dp。如果有多个顶级消费者，它们的 dp 值互不影响，直接相加就是总的食物链数量。
3.4 复杂度分析
整个算法只对每条边访问一次，每个节点入队出队各一次，时间复杂度 O(n + m)，空间复杂度 O(n + m)。这个复杂度对于 n 和 m 在 10^5 甚至 10^6 级别的数据都毫无压力，是这类题的标准最优解。
顺带一提，Kahn 算法跑完之后，如果入队的节点数量不等于 n，说明原图有环，题目保证 DAG 的情况下不会发生，但竞赛数据不健全时可以用这个判断兜底。
4. 换一种写法：记忆化搜索，两条路怎么选
4.1 自顶向下的思路反而更直观
拓扑排序 + 递推是一种"从源点往后推"的写法，需要在脑子里额外维护一个遍历顺序。另一种写法是记忆化搜索：从某个节点出发，递归计算它到终点有多少条路径，中间结果缓存起来避免重复计算。
定义 dfs(u) 返回从 u 出发能到达多少个顶级消费者。递归出口是出度为 0 的节点：如果它入度也大于 0，说明它是一条链的合法终点，返回 1；如果它是孤立点，返回 0。中间节点的计算就是 sum(dfs(v))，其中 v 是 u 的所有出边终点。因为每个节点只会被计算一次，所以总复杂度同样是 O(n + m)。如果题目数据是稠密图或者深链，递归深度会很大，需要手动调大递归限制。
4.2 参考代码（Python）
import sys from functools import lru_cache sys.setrecursionlimit(1 << 25) MOD = 80112002 def main(): n, m = map(int, sys.stdin.readline().split()) g = [[] for _ in range(n + 1)] indeg = [0] * (n + 1) outdeg = [0] * (n + 1) for _ in range(m): x, y = map(int, sys.stdin.readline().split()) g[x].append(y) # x 被 y 捕食 indeg[y] += 1 outdeg[x] += 1 @lru_cache(maxsize=None) def dfs(u): if outdeg[u] == 0: # 孤立点不算食物链终点 return 1 if indeg[u] > 0 else 0 total = 0 for v in g[u]: total = (total + dfs(v)) % MOD return total ans = 0 for i in range(1, n + 1): if indeg[i] == 0: # 从生产者开始搜索 ans = (ans + dfs(i)) % MOD print(ans) if __name__ == "__main__": main()这段代码在思路层面更接近"食物链"本身：从生产者往消费者方向走，看到出度为 0 就说明走到头了。lru_cache 自动完成记忆化，写起来很省心。但缺点也明显，Python 递归在深度达到几万层时即使设置了 setrecursionlimit，也有可能直接把进程栈压爆，导致非零退出。如果 n 特别大或者图退化成一条长链，迭代版拓扑排序更保险。
4.3 两种写法的取舍总结
说了这么多，直接给结论。
| 对比项 | 拓扑排序 + DP | 记忆化搜索 |
|---|---|---|
| 核心思路 | 自底向上递推 | 自顶向下递归 |
| 代码复杂度 | 需要额外维护入度数组和队列 | 一个递归函数就够 |
| 可读性 | 中等，需要理解拓扑序 | 较高，贴近题意 |
| 深链大图风险 | 无递归，稳定运行 | 可能爆栈 |
| 编程语言适配 | C++/Go/Java 都舒服 | Python 写起来最顺手 |
我的实际选择是：比赛或大数据的场景优先写拓扑排序迭代版，因为它稳；自己练习或者面试讲思路的时候，记忆化搜索更容易让对方理解你的推导过程。两种写法本质是同一个 DP 的两个方向，建议都实现一遍，对理解"无后效性"会有更深的体会。
5. 从 WA 到 AC：这道题最容易踩的坑
5.1 坑一：捕食方向反了，样例都救不了你
这是新手最容易踩的坑。题面写"x 被 y 捕食"，有人顺手就建一条 y->x 的边，然后发现样例输出对不上。对策是在代码注释里写清楚"边方向表示能量流向"或者"从猎物指向捕食者"，然后拿题面给的样例手动跑一遍，确认无误再提交。方向错不是逻辑问题，而是审题问题，AC 率杀手。
5.2 坑二：不认识的模数，别用肌肉记忆
这类题的模数经常不是 1e9+7，比如 80112002 这种看起来毫无规律的数字。如果你照着以往习惯写死一个模数，代码能编译能运行，答案就是错得离谱。正确做法是每次复制题面里的模数，粘贴到常量定义处，顺手确认一下是不是 int 范围内的数。别看这是个细节，很多二刷的人也会中招。
5.3 坑三：累加不取模，long long 也不一定够
如果一开始把 dp 设成 int，在模数接近 1e9 的情况下，两个 dp 值相加后很可能溢出 int，导致答案是负数或者神秘大数。即便改成 long long，如果题目后续还有乘法转移（比如带权图每条路径权重乘起来），也要先取模再做乘法，否则照样溢出。记住一个原则：涉及模数的加法、乘法，每一步都取模，不要攒到最后一次性取。
5.4 坑四：孤立点被算成一条食物链
这个坑我上面专门讲过，但实测中还是有人挂在这里。如果初始化时把所有入度为 0 的节点 dp 都设为 1，那些既没入度也没出度的孤立点就会以 dp=1 的身份进入答案统计，结果比正确答案多几个。我的习惯是用"入度为 0 且出度大于 0"严格筛选生产者，一个 if 就能挡住这个边界。
5.5 坑五：重边会让入度和路径数失真
部分题目不保证输入没有重边，比如两条完全相同的"1 被 2 吃"记录。如果不去重，入度会被重复计数，拓扑排序时同一个前驱会被算两次，dp 也会翻倍累加，相当于把同一条捕食关系当成两条不同的关系来计算。这不是题意想要的。对策是读边时用 set<pair<int, int>> 去重，或者先全部读进来，排序加 unique，再去建图和算入度。判断重边这一个小动作，能避免一场找不到原因的 WA。
6. 一个模型打天下：DAG 路径计数还能这么用
6.1 变式一：从"数量"到"最长链"只需改一行
如果题目问的不是有多少条食物链，而是最长的一条食物链包含了多少种生物，解法框架完全不动，只是把累加改成取最大值。初始化生产者 dp 为 1，转移方程写成 dp[v] = max(dp[v], dp[u] + 1)，最后在所有终点里取最大值。拓扑排序的顺序不用变，DP 的无后效性依然成立。以后遇到"关键路径""最长路径"类的题，可以直接复用这个模板。
6.2 变式二：输出一条合法食物链
有时候题目要求你输出任意一条完整食物链，那就在转移成功时顺手记录 pre[v] = u，记录 dp 是从哪个前驱更新来的。全部算完之后，从任意终点顺着 pre 数组回溯到生产者，再反转数组，就是一条合法的食物链。这个技巧在"打印方案"类题目里是通用做法，值得单独练一练。
6.3 变式三：网格图方案数也是它的亲戚
你可能没意识到，LeetCode 上"从左上角走到右下角有多少条路径"的经典题，本质也是 DAG 路径计数：网格的方向限制让每一步只能向右或向下，整张图天然无环。无论用二维数组递推还是记忆化搜索，核心思想都是"当前格子的路径数等于左边格子和上边格子路径数之和"。这和食物链计数的关系是，状态定义和转移顺序变了，底层模型没变。理解了这个，你就会明白为什么很多 DP 题都强调先建模、再定状态、最后写转移，顺序不能乱。
6.4 扩展：Kahn 拓扑排序本身还能干更多事
最后说个隐藏收益。食物链计数为了算 dp 先跑了一遍拓扑排序，这个 Kahn 算法本身就是高频考点。"课程表"系列、判断有向图是否有环、给 DAG 求一个合法执行顺序，都靠它。你把这道题吃透，等于同时掌握了 DAG 上的遍历顺序和路径统计两件事，之后再看到带"拓扑"两个字的题就不会发怵了。
7. 我在 tracker 里给这道题记了什么
既然标题里带了 tracker，最后还是分享一下我实际的记录习惯。给食物链计数这类题，我会建一行记录，大致长这样：
- 日期：当天日期
- 题目：食物链计数（牛客每日一题）
- 难度：中等
- 标签：图论 / 拓扑排序 / DAG路径DP
- 一刷结果：WA 一次（方向建反）
- 卡点：边方向、模数、孤立点边界
- 二刷日期：隔一周再写，不看题解
- 二刷结果：AC
我最想推荐的一个操作是：把"卡点"单独列出来。二刷的时候不提前看代码，只看卡点这一栏，逼自己回忆当时的错误和正确思路。如果能顺利 AC，说明真的理解了；如果还卡在同样的地方，说明上次只是背题，不是做题。这个方法我用了很久，比单纯刷题量管用得多。现在就差你把这套思路也装进自己的 tracker 里了。
