मान लीजिए कि हमारे पास एक अप्रत्यक्ष ग्राफ है, तो हमें यह जांचना होगा कि हम इसके अंदर एक विषम लंबाई चक्र ढूंढ सकते हैं या नहीं।
तो, अगर इनपुट 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) सत्य है, तो
- सही लौटें
- यदि 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