उन जानवरों की न्यूनतम संख्या गिनने का कार्यक्रम जिनका पायथन में कोई शिकारी नहीं है

मान लीजिए कि हमारे पास संख्याओं की एक सूची है, जिसे nums कहा जाता है, जहां nums[i] ith जानवर के शिकारी को दिखाता है और यदि कोई शिकारी नहीं है, तो यह -1 धारण करेगा। हमें जानवरों के समूहों की सबसे छोटी संख्या का पता लगाना है ताकि कोई भी जानवर अपने प्रत्यक्ष या अप्रत्यक्ष शिकारी के समूह में न हो।

इसलिए, यदि इनपुट nums =[1, 2, −1, 4, 5, −1] जैसा है, तो आउटपुट 3 होगा, क्योंकि हमारे पास इस तरह के समूह हो सकते हैं:[0, 3], [1, 4 ], [2, 5]।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

अगर A खाली है, तो
- वापसी 0
adj :=एक खाली नक्शा
vis :=एक नया सेट
जड़ें :=एक नई सूची
प्रत्येक इंडेक्स के लिए मैं और ए में मूल्य ए, करो
- अगर a −1 के समान है, तो
  - जड़ों के अंत में i डालें
- adj[i]
  . के अंत में a डालें
- adj[a]
  . के अंत में i डालें
श्रेष्ठ :=−अनंतता
जड़ों में प्रत्येक जड़ के लिए, करें
- stk :=एक स्टैक और उसमें [रूट, 1] डालें
- जबकि stk खाली नहीं है, करें
  - (नोड, डी) :=stk का पॉपड एलिमेंट
  - यदि नोड विज़ में है या नोड -1 के समान है, तो
    - लूप से बाहर आएं
  - श्रेष्ठ :=अधिकतम सर्वोत्तम और d
  - विज़ में नोड डालें
  - adj[नोड] में प्रत्येक यू के लिए, करें
    - पुश (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]