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

ধরুন আমাদের কাছে 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]

আউটপুট

3