我们已经涉及了微观（DNA、细胞）、遗传（多基因）、生理（生长素、光合作用）。这次我们将目光投向 宏观生态学，具体是高中生物必修三《稳态与环境》中 生态系统的结构 这一章节。

这道题目考察的是图论（Graph Theory）的基础应用，具体是有向无环图（DAG）的遍历，通常使用记忆化搜索（DFS + Memoization）或动态规划来解决。难度定位 GESP 5级（CSP-J T3 难度）。

---

题目：复杂的食物网 (The Complex Food Web)

【背景知识讲解】

在生态系统中，生物之间因为捕食关系而构成了一条条食物链。多条食物链彼此交错连接，形成了食物网。

**营养级（Trophic Level）**是描述生物在食物链中所处位置的概念：

1. 第一营养级：生产者（主要是绿色植物），它们不捕食其他生物，直接利用太阳能。规定其营养级为 $1$。
2. 第二营养级：初级消费者（植食性动物），以生产者为食。营养级为 $2$。
3. 第三营养级：次级消费者（肉食性动物），以初级消费者为食。
4. 以此类推...

注意：在复杂的食物网中，同一种生物可能处于不同的营养级。例如，人吃米饭时是第二营养级，吃牛肉时是第三营养级。 在生物学计算中，为了评估一个物种在生态系统中的最高地位，我们通常关注它所在的最高营养级（即在最长的那条食物链中的位置）。

【题目描述】

生态学家在一个封闭的岛屿上发现了 $N$ 个物种，编号从 $1$ 到 $N$。 经过长期的观察，记录下了 $M$ 组捕食关系。每组关系描述为“生物 A 捕食 生物 B”。

在这个生态系统中：

1. 生产者定义为：不捕食任何其他已知物种的生物。它们的营养级固定为 $1$。
2. 消费者的营养级定义为：$1 +$ 它所捕食的生物的最高营养级。
   • 公式：$L(A) = 1 + \max(L(B_1), L(B_2), \dots)$，其中 $A$ 捕食 $B_1, B_2 \dots$。

请你帮助生态学家计算，在这个食物网中，最高的营养级数值是多少？（即所有物种里，营养级最大的那个值）。

注意：

• 题目保证给出的食物网是一个有向无环图（DAG），不存在“A吃B，B吃C，C吃A”这种循环捕食的情况。
• 如果一个物种既不捕食别人，也不被别人捕食，它也是生产者，营养级为 1。

【输入格式】

第一行包含两个整数 $N$ 和 $M$，分别表示物种数量和捕食关系的数量。 接下来 $M$ 行，每行包含两个整数 $U, V$，表示 物种 $U$ 捕食 物种 $V$（即能量从 $V$ 流向 $U$）。

【输出格式】

输出一个整数，表示该生态系统中存在的最大营养级数值。

【样例数据】

输入：

5 4
2 1
3 2
4 2
5 3

输出：

4

样例解释： 捕食关系如下：

• 2 吃 1
• 3 吃 2
• 4 吃 2
• 5 吃 3

推导过程：

1. 物种 1：不捕食任何人 $\rightarrow$ 生产者，营养级 = 1。
2. 物种 2：吃 1。营养级 = $1 + L(1) = 2$。
3. 物种 3：吃 2。营养级 = $1 + L(2) = 3$。
4. 物种 4：吃 2。营养级 = $1 + L(2) = 3$。
5. 物种 5：吃 3。营养级 = $1 + L(3) = 4$。

所有物种的营养级为 $\{1, 2, 3, 3, 4\}$。最大值为 4。

【数据范围】

• 对于 100% 的数据：$1 \le N \le 100,000$，$0 \le M \le 200,000$。
• 保证数据合法，无环。

---

一、 思路提示

1. 图的表示：

   • 题目给出的关系是 "$U$ 吃 $V$"。我们可以把它看作一条有向边 $U \to V$。
   • 为了计算 $U$ 的等级，我们需要知道它吃的 $V$ 的等级。这是一种递归的关系。
   • 数据结构：我们可以用邻接表（vector<vector<int>>）来存储图。为了方便计算，存 $U$ 吃 $V_1, V_2...$ 比较好。

2. 递归与重复计算：

   • 如果我们想算“老鹰”的等级，就要算“蛇”的等级；算“蛇”就要算“青蛙”……直到算出“草”（生产者）。
   • 如果直接写递归函数 getLevel(u)，可能会有大量重复计算。比如“蛇”既被“老鹰”吃，也被“猫头鹰”吃，那“蛇”的等级会被算两次。
   • 在 $N=10^5$ 的情况下，普通递归会超时。

3. 记忆化搜索（Memoization）：

   • 这是解决此类问题的金钥匙。
   • 开一个数组 memo[N]，初始化为 0。
   • 当我们需要算 getLevel(u) 时：
     • 先检查 memo[u] 是否不为 0。如果是，直接返回（之前算过了）。
     • 如果没算过，遍历 $U$ 吃的所有猎物 $V$，找出 $V$ 中最大的等级 max_v_level。
     • 计算出结果 ans = 1 + max_v_level。
     • 存入 memo[u] = ans。
     • 返回 ans。

4. 寻找生产者：

   • 递归的终止条件是什么？
   • 如果一个生物 $U$ 的邻接表是空的（它不吃任何东西），那么它的等级就是 1。

---

二、 预备知识点总结

1. 图的存储：邻接表 vector<int> adj[N]。
2. 深度优先搜索 (DFS)：递归函数的编写。
3. 记忆化 (Memoization)：用数组记录函数返回值，避免重复计算，将指数级复杂度降为线性复杂度 $O(N+M)$。

---

三、 启发式教学：草稿纸上的推理过程

教练：“我们把生物画成圆圈，谁吃谁就画个箭头。”

场景：

• 草(1)
• 兔子(2) 吃 草(1)
• 狼(3) 吃 兔子(2)
• 蘑菇(4) [分解者，这里假设它也吃兔子尸体?] -> 不，题目说生产者不捕食。那假设有个特殊的 蘑菇(4) 吃 草(1)。

画图：

3(狼) -> 2(兔) -> 1(草)
         ^
         |
      4(狐狸)

假设关系：狼吃兔，狐狸吃兔。

推理：

1. 我想知道狼是几级？
   • 看狼吃谁？吃兔。
   • 那兔是几级？不知道，先去算兔。
2. 算兔：
   • 看兔吃谁？吃草。
   • 那草是几级？不知道，算草。
3. 算草：
   • 草吃谁？谁都不吃。
   • Bingo! 草是 1 级。
   • 回得去告诉兔：草是 1。
4. 回溯到兔：
   • 兔 = 1 + 草(1) = 2 级。
   • 记下来！兔是 2 级。（下次狐狸来问的时候，直接告诉它是 2，不用再去找草了）。
5. 回溯到狼：
   • 狼 = 1 + 兔(2) = 3 级。

算法总结： 遍历每一个生物，问它“你是几级？”。它会去问它的午餐。如果问过了（有记录），直接回答；没问过，就一路问到底。

---

四、 读题关键词总结

1. “最大” / “最高” $\rightarrow$ max 操作，通常涉及 DP 或 贪心，这里是 DP/记忆化。
2. “$N=100,000$” $\rightarrow$ 必须是线性复杂度 $O(N+M)$，不能用 $O(N^2)$。
3. “无环” $\rightarrow$ 放心用递归，不会死循环。
4. “捕食” $\rightarrow$ 有向边的方向。输入是 $U$ 吃 $V$，还是 $V$ 被 $U$ 吃，一定要看清。本题是 $U$ 吃 $V$。

---

五、 标准题解代码 (C++14)

见题解

这道题以生态系统食物网为模型，非常自然地引入了图的遍历和记忆化搜索算法。通过“营养级”的计算，学生不仅能巩固 DFS 的写法，还能深刻理解为什么需要“记忆化”来降低复杂度。