CF2041K.Trophic Balance Species

图像由 ChatGPT 4o 生成。在一项跨学科的合作中，一位生态系统科学家与一位计算机科学家联手，通过计算方法分析复杂生态系统的结构。生态系统科学家将整个系统建模成一个有向图 $D = (V, A)$，其中每个物种用一个节点 $v \in V$ 表示，每一对捕食关系由从被捕食者 $x$ 到捕食者 $y$ 的有向边 $(x, y) \in A$ 表示。这种图的结构可以用来模拟生态系统中能量在不同物种间的流动。

在这个系统中，有两个重要概念：

• 独立营养群：如果集合 $S$ 中的任何物种 $x \in S$ 无法通过一系列有向捕食关系到达集合 $S$ 中的其他物种 $y \in S$（其中 $y \ne x$），那么这个集合 $S$ 就是一个独立营养群，即从 $x$ 到 $y$ 没有有向路径。

• 营养平衡物种：一个物种如果它受到的影响来自直接或间接捕食者的数量（可以通过有向路径到达的物种，不包括自身）和来自直接或间接被捕食者的数量（可以通过有向路径达到该物种，不包括自身）之间的差值在所有物种中最小，就称为营养平衡物种。

考虑一个含有 $n = 4$ 个物种和 $m = 3$ 条捕食关系的生态系统：

• 物种 1：草（节点 1）
• 物种 2：兔子（节点 2）
• 物种 3：狐狸（节点 3）
• 物种 4：鹰（节点 4）

捕食关系用以下有向边表示：

• $(1, 2)$：草被兔子吃掉。
• $(2, 3)$：兔子被狐狸吃掉。
• $(2, 4)$：兔子也被鹰吃掉。

现在，考虑集合 $S = \{3, 4\}$（狐狸和鹰）。在节点 3（狐狸）和节点 4（鹰）之间没有有向路径；狐狸无法到达鹰，而鹰也无法到达狐狸。因此，这个集合符合独立营养群的定义。

接下来看各物种情况：

• 物种 1（草）：

  • 能到达的物种数：3（兔子、狐狸、鹰）
  • 能被到达的物种数：0（无）
  • 绝对差值：$|3 - 0| = 3$

• 物种 2（兔子）：

  • 能到达的物种数：2（狐狸、鹰）
  • 能被到达的物种数：1（草）
  • 绝对差值：$|2 - 1| = 1$

• 物种 3（狐狸）：

  • 能到达的物种数：0（无）
  • 能被到达的物种数：2（来自草和兔子）
  • 绝对差值：$|0 - 2| = 2$

• 物种 4（鹰）：

  • 能到达的物种数：0（无）
  • 能被到达的物种数：2（来自草和兔子）
  • 绝对差值：$|0 - 2| = 2$

在这些物种中，兔子的绝对差值最小，为 1，因此，兔子被认为是该生态系统的营养平衡物种。

题目已知生态系统中任何独立营养群的大小最多为 $k$。你的任务是找到生态系统中所有的营养平衡物种。

第一行包含两个整数 $n$ 和 $m$，其中 $n$ 代表节点数，$m$ 代表边数。这些节点是编号为 $1, 2, \ldots, n$ 的物种。接下来的 $m$ 行，每一行包含两个整数 $x_i$ 和 $y_i$，表示有一条从节点 $x_i$ 指向节点 $y_i$ 的有向边。

• $1 \le n \le 2 \times 10^5$
• $0 \le m \le \min\{n(n-1), 4 \times 10^5\}$
• $k$ 不是输入数据，但保证 $1 \le k \le 16$
• 对于每一个 $i$（$1 \le i \le m$），$1 \le x_i, y_i \le n$ 且 $x_i \ne y_i$
• 在输入中，任意有序对 $(x_i, y_i)$ 最大只出现一次

在一行上输出所有营养平衡物种的节点编号，升序排列。节点编号之间用空格分隔。

本翻译由 AI 自动生成

null