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