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

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

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

समाधान दृष्टिकोण

इस समस्या को हल करने के लिए हम DFS का उपयोग करेंगे जो पथ में नोड की गहराई को ट्रैक करता है:

• dfs(node, i) फंक्शन परिभाषित करें:
  • यदि node, path में है, तो (i - path[node]) विषम है तो True लौटाएं
  • यदि node visited है, तो False लौटाएं
  • node को visited मार्क करें
  • path[node] := i
  • arr[node] में प्रत्येक c के लिए:
    • यदि dfs(c, i + 1) True है, तो True लौटाएं
  • path[node] हटाएं
  • False लौटाएं
• मुख्य मेथड में:
  • visited := एक नया सेट, path := एक नया मैप
  • i को 0 से arr के आकार - 1 तक लूप चलाएं:
    • यदि dfs(i, 0) True है, तो True लौटाएं
  • False लौटाएं

पायथन कार्यान्वयन

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