मान लीजिए हमारे पास एक अविकल्पित ग्राफ है, हमें जांचना है कि ग्राफ द्विभाजित है या नहीं। जैसा कि हम जानते हैं, एक ग्राफ द्विभाजित होता है जब हम ग्राफ के नोड्स को दो सेट 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लेगा। - ग्राफ[
source] में प्रत्येक शीर्ष के लिए:- यदि
color[vertex]-1 के समान नहीं है, तो:- यदि
color[vertex],color[source]के समान है, तोresult[0] := Falseऔर लौटें। - अगले पुनरावृत्ति के लिए जारी रखें।
- यदि
color[vertex] := 1 - color[source]dfs(vertex)
- यदि
- मुख्य विधि से:
n := arrका आकार।graph:= 0 सेn-1शीर्षों के लिए खाली आसन्न सूची।iको 0 सेnतक:arr[i]में प्रत्येकjके लिए:iकोgraph[j]में डालें।jकोgraph[i]में डालें।
color:= आकारnकी सूची, -1 से भरी हुई।result:= एकTrueमान वाली सूची।
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