मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है जहां nums[i] iवें जानवर के शिकारी को दर्शाता है और यदि कोई शिकारी नहीं है, तो यह -1 रखेगा। हमें जानवरों के समूहों की सबसे छोटी संख्या ढूंढनी है जैसे कि कोई जानवर अपने प्रत्यक्ष या अप्रत्यक्ष शिकारी के साथ एक ही समूह में न हो।
इसलिए, यदि इनपुट nums = [1, 2, -1, 4, 5, -1] जैसा है, तो आउटपुट 3 होगा, क्योंकि हमारे पास [0, 3], [1, 4], [2, 5] जैसे समूह हो सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
यदि A खाली है, तो
0 वापस करें
adj := एक खाली मैप
vis := एक नया सेट
roots := एक नई सूची
प्रत्येक इंडेक्स i और मान a के लिए 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 := best और d का अधिकतम
node को vis में जोड़ें
प्रत्येक u के लिए adj[node] में, करें
(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]
आउटपुट
3
