मान लीजिए हमारे पास एक संख्या n और enemies नामक एक 2D मैट्रिक्स है। यहां n इंगित करता है कि 0 से n-1 तक लेबल वाले n लोग हैं। अब enemies में प्रत्येक पंक्ति में [a, b] होता है जिसका अर्थ है कि a और b दुश्मन हैं। हमें यह जांचना है कि क्या n लोगों को दो समूहों में विभाजित करना संभव है जैसे कि कोई भी दो लोग जो दुश्मन हैं, एक ही समूह में न हों।
इसलिए, यदि इनपुट n = 4, enemies = [[0, 3],[3, 2]] जैसा है, तो आउटपुट True होगा, क्योंकि हमारे पास [0, 1, 2] और [3] जैसे दो समूह हो सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
graph := एक खाली एडजेंसी सूची
प्रत्येक दुश्मन जोड़ी (u, v) के लिए enemies में, करें
v को graph[u] के अंत में जोड़ें
u को graph[v] के अंत में जोड़ें
color := एक नया मैप
एक फ़ंक्शन dfs() परिभाषित करें। यह u, c := 0 को प्रारंभ में लेगा
यदि u, color में है, तो
true वापस करें जब color[u], c के समान हो
color[u] := c
प्रत्येक v के लिए graph[u] में dfs(v, c XOR 1) के सभी true होने पर true वापस करें
मुख्य विधि से निम्नलिखित करें −
प्रत्येक u के लिए 0 से n तक की रेंज में यदि u, color में नहीं है तो dfs(u) के सभी true होने पर true वापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
उदाहरण
class Solution: def solve(self, n, enemies): from collections import defaultdict graph = defaultdict(list) for u, v in enemies: graph[u].append(v) graph[v].append(u) color = {} def dfs(u, c=0): if u in color: return color[u] == c color[u] = c return all(dfs(v, c ^ 1) for v in graph[u]) return all(dfs(u) for u in range(n) if u not in color) ob = Solution() n = 4 enemies = [[0, 3],[3, 2]] print(ob.solve(n, enemies))इनपुट
4, [[0, 3],[3, 2]]
आउटपुट
True
