由 ChatGPT 4o 生成的图像。
在跨学科合作中,生态系统科学家和计算机科学家联手使用计算方法分析复杂生态系统的结构。生态系统科学家将生态系统建模为有向图 $$$D = (V, A)$$$,其中每个物种由 V$$$ 中的节点 $$$v \in 表示,每个进食关系表示为 A$$$ 中从猎物 $$$x$$$ 到捕食者 $$$y$$$ 的有向边 $$$(x, y) \in A$$$。这种图形结构使他们能够模拟整个生态系统中从一个物种到另一个物种的能量流动。
定义了生态系统的两个基本特征:
- 独立营养群:如果没有物种 $$$x \in S$$$ 可以通过一系列定向喂养关系到达另一个物种 $$$y \in S$$$(对于某些 $$$y \ne x$$$),则一组 $$$S$$$ 动物物种被归类为独立营养群,这意味着 $$$D$$$ 中不存在从 $$$x$$$ 到 $$$D$$$ 的定向路径$$$y$$$。
- 营养平衡物种:如果一个物种拥有几乎相等数量的直接或间接影响它的掠食者物种(它可以通过 $$$D$$$ 中的定向路径到达的物种,不包括其自身)和直接或间接影响它的猎物物种(可以通过 $$$D$$$ 中的定向路径到达它的物种,不包括其自身),则该物种被称为营养平衡物种。具体来说,营养平衡物种是指生态系统中所有物种中上述两个数字之间的绝对差值最小的物种。
考虑一个具有 $$$n = 4$$$ 物种和 $$$m = 3$$$ 喂养关系的生态系统:
- 物种 1:草(节点 1)
- 物种 2:兔子(节点 2)
- 物种 3:狐狸(节点 3)
- 物种 4:鹰(节点 4)
表示进给关系的有向边如下:
- $$$(1, 2)$$$:草被兔子吃掉了。
- $$$(2, 3)$$$:兔子被狐狸吃掉。
- $$$(2, 4)$$$:兔子也会被老鹰吃掉。
现在,考虑集合 $$$S=\{3,4\}$$$ (狐狸和鹰)。 Foxes(节点 3)和 Hawks(节点 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$$$)表示由所研究的生态系统引起的有向图 $$$D$$$ 中的节点数(分别为边)。节点编号为 $$$1, 2, \ldots, n$$$。然后是 $$$m$$$ 行。第$$$i$$$行包含两个整数$$$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\neq y_i$$$。
- 每个有序对 $$$(x_i, y_i)$$$ 在输入中最多出现一次。
输出
在单行上按升序输出所有营养平衡物种的节点标识符。对于任意两个连续的节点标识符,用空格分隔它们。
示例
输入 #1
4 3 1 2 2 3 2 4
输出 #1
2
输入 #2
4 5 1 2 1 3 1 4 2 3 3 2
输出 #2
2 3 4