Giả sử chúng ta có một đồ thị vô hướng, chúng ta phải kiểm tra xem đồ thị có phải là lưỡng phân hay không. Như chúng ta đã biết một đồ thị là lưỡng phân khi chúng ta có thể chia các nút của đồ thị thành hai tập A và B sao cho mọi cạnh {u, v} trong đồ thị có một nút u ở A và một nút khác v ở B.
Vì vậy, nếu đầu vào giống như
Khi đó đầu ra sẽ là True, [0,4] nằm trong tập A và [1,2,3] nằm trong tập B và tất cả các cạnh từ A đến B hoặc B thành A, không phải A đến A hoặc B đến B .
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau−
-
Định nghĩa một hàm dfs (). Điều này sẽ lấy nguồn
-
đối với mỗi đỉnh trong biểu đồ [nguồn], thực hiện
-
nếu màu [đỉnh] không giống -1 thì
-
nếu màu [đỉnh] giống với màu [nguồn] thì
-
kết quả [0]:=Sai
-
trở lại
-
-
chuyển sang lần lặp tiếp theo
-
-
color [vertex]:=1 - color [source]
-
dfs (đỉnh)
-
-
Từ phương thức chính, hãy thực hiện như sau−
-
n:=kích thước của arr
-
graph:=danh sách kề rỗng cho các đỉnh từ 0 đến n-1
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
đối với mỗi j trong arr [i], thực hiện
-
chèn i vào biểu đồ [j]
-
chèn j vào biểu đồ [i]
-
-
color:=danh sách kích thước n và điền -1
-
result:=danh sách có một giá trị True
-
-
đối với tôi trong phạm vi từ 0 đến n, hãy thực hiện
-
nếu màu [i] giống -1 thì
-
dfs (i)
-
-
trả về kết quả [0]
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))
Đầu vào
graph = [[1,2,3],[0],[0,4],[0,4],[2,3]]
Đầu ra
True