उन व्यक्तियों को अलग करने का कार्यक्रम जहां कोई भी दुश्मन पायथन में एक ही समूह में नहीं रह सकता है

मान लीजिए कि हमारे पास एक संख्या n और एक 2D मैट्रिक्स है जिसे दुश्मन कहा जाता है। यहां n इंगित करता है कि [0, n - 1] से लेबल किए गए n लोग हैं। अब शत्रुओं की प्रत्येक पंक्ति में [a, b] होता है जिसका अर्थ है कि a और b शत्रु हैं। हमें यह जांचना होगा कि क्या n लोगों को दो समूहों में विभाजित करना संभव है ताकि कोई भी दो लोग जो दुश्मन हों, एक ही समूह में न हों।

इसलिए, यदि इनपुट n =4, शत्रु =[[0, 3], [3, 2]] जैसा है, तो आउटपुट सही होगा, क्योंकि हमारे पास ये दो समूह [0, 1, 2] और [ 3].

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• ग्राफ़ :=एक खाली आसन्न सूची

• दुश्मनों में प्रत्येक दुश्मन जोड़ी (यू, वी) के लिए, करें

  • ग्राफ़ के अंत में v डालें[u]

  • ग्राफ़ के अंत में आपको डालें[v]

• रंग :=एक नया नक्शा

• फ़ंक्शन को परिभाषित करें dfs() । यह आपको ले जाएगा, c :=0 शुरू में

• अगर आप रंग में हैं, तो

  • जब रंग [u] c के समान हो तो सही लौटें

• रंग [यू] :=सी

• ग्राफ़ में प्रत्येक वी के लिए सभी dfs(v, c XOR 1) जब सही हो [u] सत्य हो

• मुख्य विधि से निम्न कार्य करें -

• जब सभी (dfs(u) प्रत्येक u के लिए 0 से n की श्रेणी में हों और यदि u रंग में नहीं है) सत्य हो तो सत्य वापस लौटें

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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