পাইথনে কোন শিকারী নেই এমন প্রাণীর ন্যূনতম সংখ্যা গণনা করার প্রোগ্রাম

ধরুন আমাদের কাছে nums নামে একটি সংখ্যার তালিকা রয়েছে যেখানে nums[i] ith প্রাণীর শিকারীকে দেখায় এবং যদি কোন শিকারী না থাকে তবে এটি −1 ধরে রাখবে। আমাদের প্রাণীদের ক্ষুদ্রতম সংখ্যক গোষ্ঠী খুঁজে বের করতে হবে যেন কোনো প্রাণী তার প্রত্যক্ষ বা পরোক্ষ শিকারীর সাথে একই দলে না থাকে।

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[1, 2, −1, 4, 5, −1], তাহলে আউটপুট হবে 3, আমাদের যেমন গ্রুপ থাকতে পারে:[0, 3], [1, 4] ], [২, ৫]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

যদি A খালি হয়, তাহলে
- রিটার্ন 0
adj :=একটি ফাঁকা মানচিত্র
ভিস :=একটি নতুন সেট
roots :=একটি নতুন তালিকা
প্রতিটি সূচক i এবং A এর মান A এর জন্য করুন
- a যদি −1 এর সমান হয়, তাহলে
  - মূলের শেষে i ঢোকান
- adj[i]
  এর শেষে একটি সন্নিবেশ করান
- adj[a]
  এর শেষে i ঢোকান
সেরা :=−অসীম
প্রতিটি মূলের জন্য, করুন
- stk :=একটি স্ট্যাক এবং এটিতে [root, 1] ঢোকান
- stk খালি না থাকার সময়, করুন
  - (নোড, ডি) :=stk
    এর পপ করা উপাদান
  - যদি নোড ভিসে থাকে বা নোড −1 এর মত হয়, তাহলে
    - লুপ থেকে বেরিয়ে আসুন
  - সেরা :=সর্বোত্তম এবং ডি
  - ভিসে নোড সন্নিবেশ করান
  - adj[নোড]-এ প্রতিটি 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]