题目理解

这是一个食物网，物种编号 $1$ 到 $n$，能量流动关系 $a_i \to b_i$ 表示 $a_i$ 被 $b_i$ 捕食（能量从 $a_i$ 流向 $b_i$）。

食物链的定义：从某个生产者（没有捕食者，即入度为 0）开始，到某个顶级消费者（没有猎物，即出度为 0）结束的一条路径。

注意：单独一个孤立生物不算一条食物链。

题目要求计算所有不同的食物链条数。

算法思路

1. 建模
   将食物网看作一个有向图，$a_i \to b_i$ 表示 $a_i$ 是 $b_i$ 的食物（能量从 $a_i$ 流向 $b_i$）。
   在生态学中，这意味着 $b_i$ 捕食 $a_i$，所以图中箭头方向是“被捕食者 → 捕食者”。

2. 起点与终点

   • 起点：生产者（入度 = 0 的节点）
   • 终点：顶级消费者（出度 = 0 的节点）

3. 统计路径数
   我们可以用动态规划（DP） 来做：
   设 $dp[u]$ 表示从某个生产者开始，到达节点 $u$ 的路径条数。
   初始时，对于每个生产者 $p$，$dp[p] = 1$。
   然后按拓扑排序的顺序更新：

   $$dp[v] += dp[u] \quad \text{当存在边} \ u \to v$$

   最终答案是所有顶级消费者（出度 = 0）的 $dp$ 值之和。

4. 注意

   • 单独一个节点（既是生产者又是顶级消费者）不算一条食物链，所以这种情况不计入答案。
   • 题目保证输入符合生物学特点，所以不会出现环。

复杂度分析

• 拓扑排序：$O(n + m)$
• 空间复杂度：$O(n + m)$