मान लीजिए हमारे पास एक अनिर्देशित ग्राफ है, हमें जांचना है कि ग्राफ बाइपार्टाइट है या नहीं। जैसा कि हम जानते हैं, एक ग्राफ बाइपार्टाइट होता है जब हम ग्राफ के नोड्स को दो सेट A और B में विभाजित कर सकते हैं जैसे कि ग्राफ में हर एज {u,v} का एक नोड u A में और दूसरा नोड v B में हो।
उदाहरण के लिए, यदि इनपुट है
तो आउटपुट होगा True, [0,4] सेट A में हैं और [1,2,3] सेट B में हैं, और सभी एज A से B या B से A हैं, A से A या B से B नहीं।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- एक फ़ंक्शन dfs() परिभाषित करें। यह source लेगा
- graph[source] में प्रत्येक वर्टेक्स के लिए, करें
- यदि color[vertex], -1 के समान नहीं है, तो
- यदि color[vertex], color[source] के समान है, तो
- result[0] := False
- वापस करें
- अगले पुनरावृत्ति के लिए जाएं
- यदि color[vertex], color[source] के समान है, तो
- color[vertex] := 1 - color[source]
- dfs(vertex)
- यदि color[vertex], -1 के समान नहीं है, तो
- मुख्य विधि से, निम्नलिखित करें:
- n := arr का आकार
- graph := वर्टेक्स 0 से n-1 के लिए खाली आसन्न सूची
- i के लिए 0 से n तक की रेंज में, करें
- arr[i] में प्रत्येक j के लिए, करें
- i को graph[j] में डालें
- j को graph[i] में डालें
- color := आकार n की एक सूची और -1 से भरें
- result := एक True मान वाली सूची
- arr[i] में प्रत्येक j के लिए, करें
- i के लिए 0 से n तक की रेंज में, करें
- यदि color[i], -1 के समान है, तो
- dfs(i)
- result[0] वापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
উদাহরণ
from collections import defaultdict class Solution: def solve(self, arr): n = len(arr) graph = [set() for i in range(n)] for i in range(n): for j in arr[i]: graph[j].add(i) graph[i].add(j) color = [-1] * n result = [True] def dfs(source): for child in graph[source]: if color[child] != -1: if color[child] == color[source]: result[0] = False return continue color[child] = 1 - color[source] dfs(child) for i in range(n): if color[i] == -1: dfs(i) return result[0] ob = Solution() graph = [[1,2,3],[0],[0,4],[0,4],[2,3]] print(ob.solve(graph))
इनपुट
graph = [[1,2,3],[0],[0,4],[0,4],[2,3]]
आउटपुट
True
