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について、実行します

  • aが-1と同じ場合、

    • ルートの最後にiを挿入します

  • adj [i]

    の最後にaを挿入します

  • adj [a]

    の最後にiを挿入します

• 最高：=−無限大

• ルート内のルートごとに、実行します

  • stk：=スタックし、[root、1]をスタックに挿入します

  • stkが空でない間、実行します

    • （ノード、d）：=stkのポップされた要素

    • ノードがvisにあるか、ノードが-1と同じである場合、

      • ループから出てきます

    • best：=bestとdの最大値

    • visにノードを挿入

    • adj [node]のuごとに、実行

      • （u、d + 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