用 Python 编写程序来计算没有捕食者的动物的最小数量

pythonserver side programmingprogramming更新于 2026/2/3 22:04:17

假设我们有一个名为 nums 的数字列表，其中 nums[i] 表示第 i 个动物的捕食者，如果没有捕食者，它将保留 −1。我们必须找到最少数量的动物组，使得没有动物与其直接或间接捕食者属于同一组。

因此，如果输入为 nums = [1, 2, −1, 4, 5, −1]，则输出将为 3，因为我们可以有以下组:[0, 3], [1, 4], [2, 5]。

为了解决这个问题，我们将遵循以下步骤 −

如果 A 为空，则
- 返回 0
adj := 一个空白映射
vis := 一个新集合
roots := 一个新列表
对于每个索引 i 和 A 中的值 a，执行
- 如果 a 与 −1 相同，则
  - 在 roots 末尾插入 i
- 在 adj[i] 末尾插入 a
- 在 adj[a] 末尾插入 i
best := −infinity
对于 roots 中的每个 root，执行
- stk := 堆栈并将 [root, 1] 插入其中
- 当 stk 不为空时，执行
  - (node, d) := 弹出元素stk
  - 如果节点在 vis 中或节点与 −1 相同，则
    - 退出循环
  - best := best 和 d 的最大值
  - 将节点插入 vis
  - 对于 adj[node] 中的每个 u，执行
    - 将 (u, d + 1) 推送到 stk
返回 best

让我们看看下面的实现以便更好地理解 −

示例

from collections import defaultdict
class Solution:
   def solve(self, A):
      if not A:
         return 0
      adj = defaultdict(list)
      vis = set()
      roots = []
      for i, a in enumerate(A):
         if a == -1:
            roots.append(i)
         adj[i].append(a)
         adj[a].append(i)
      best = −float("inf")
      for root in roots:
      stk = [(root, 1)]
      while stk:
         node, d = stk.pop()
         if node in vis or node == −1:
            continue
         best = max(best, d)
         vis.add(node)
         for u in adj[node]:
            stk.append((u, d + 1))
   return best
ob = Solution()
nums = [1, 2, −1, 4, 5, −1]
print(ob.solve(nums))