该程序计算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