该程序计算Python中没有捕食者的最小动物数量

假设我们有一个称为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

• 在根的末尾插入i

• 如果a与-1相同，则

• 在adj [i]的末尾插入a

• 在adj [a]的末尾插入i

• 最佳：=-无穷大

• 对于根中的每个根，

• （节点，d）：= stk的弹出元素

• 如果node在vis或node与-1相同，则

• 最佳：=最佳和d的最大值

• 将节点插入vis

• 对于adj [node]中的每个u，执行

• 从循环中出来

• 将（u，d + 1）推入stk

• stk：=一个堆栈，并在其中插入[root，1]

• 当stk不为空时，执行

• 最好的回报

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

示例

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))

输入值

[1, 2, −1, 4, 5, −1]

输出结果

3