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

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

যদি ইনপুট হয় nums = [1, 2, -1, 4, 5, -1], তবে আউটপুট হবে ৩, কারণ আমরা গ্রুপ বানাতে পারি: [0, 3], [1, 4], [2, 5]।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:

যদি A খালি হয়, তবে ০ ফেরত দিন।
adj := একটি খালি ম্যাপ।
vis := একটি নতুন সেট।
roots := একটি নতুন তালিকা।
A-তে থাকা প্রতিটি ইনডেক্স i এবং মান a-এর জন্য:
- যদি a == -1 হয়, তবে i কে roots-এ যোগ করুন।
- a কে adj[i]-এ যোগ করুন।
- i কে adj[a]-এ যোগ করুন।
best := -infinity
প্রতিটি root-এ roots-এ জন্য:
- stk := একটি স্ট্যাক এবং [root, 1] ডালুন।
- যখন stk খালি না হয়:
  - (node, d) := stk থেকে পপ করুন।
  - যদি node vis-এ থাকে বা node == -1, তবে লুপ থেকে বের হোন।
  - best := max(best, d)
  - node কে vis-এ যোগ করুন।
  - adj[node]-এ থাকা প্রতিটি u-এর জন্য (u, d + 1) stk-এ পুশ করুন।
best ফেরত দিন।

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:

উদাহরণ

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]