पायथन में विषम लंबाई चक्र एक ग्राफ में है या नहीं यह जांचने के लिए कार्यक्रम

मान लीजिए कि हमारे पास एक अप्रत्यक्ष ग्राफ है, तो हमें यह जांचना होगा कि हम इसके अंदर एक विषम लंबाई चक्र ढूंढ सकते हैं या नहीं।

तो, अगर इनपुट adj_list =[[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]

तब आउटपुट सही होगा क्योंकि [0, 1, 3, 4, 2], [1, 3, 4], [2, 3, 4] जैसे विषम लंबाई के चक्र हैं।

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

• एक फ़ंक्शन को परिभाषित करें dfs() । यह नोड लेगा, मैं
• यदि नोड पथ में है, तो
  • सही लौटें जब (i - पथ[नोड]) विषम हो
• यदि नोड का दौरा किया जाता है, तो
  • झूठी वापसी
• नोड को विज़िट किया गया के रूप में चिह्नित करें
• पथ[नोड] :=i
• गिरफ्तारी में प्रत्येक सी के लिए[नोड], करते हैं
  • यदि dfs(c, i + 1) सत्य है, तो
    • सही लौटें
• डेल पथ[नोड]
• झूठी वापसी
• मुख्य विधि से निम्न कार्य करें -
• विज़िट किया:=एक नया सेट, पथ:=एक नया नक्शा
• मेरे लिए 0 से लेकर गिरफ्तारी के आकार तक, करें
• यदि dfs(i, 0) सत्य है, तो
• सही लौटें
• झूठी वापसी

उदाहरण (पायथन)

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

class Solution:
   def solve(self, arr):
      def dfs(node, i):
         if node in path:
            return (i - path[node]) % 2 == 1
         if node in visited:
            return False
         visited.add(node)
         path[node] = i
         for c in arr[node]:
            if dfs(c, i + 1):
               return True
         del path[node]
         return False
      visited, path = set(), {}
      for i in range(len(arr)):
         if dfs(i, 0):
            return True
      return False
ob = Solution()
adj_list = [[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]
print(ob.solve(adj_list))

इनपुट

[[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]

आउटपुट

True