Chương trình kiểm tra đồ thị có phải hai phần hay không trong Python

Cho một đồ thị vô hướng, kiểm tra xem nó có phải đồ thị hai phần (bipartite) hay không. Đồ thị hai phần khi có thể chia tập đỉnh thành hai tập A và B sao cho mọi cạnh {u,v} đều có một đỉnh trong A và một đỉnh trong B.

Ví dụ, đồ thị: Đầu ra là True, vì tập A = {0,4}, tập B = {1,2,3}, mọi cạnh đều nối giữa A và B.

Các bước giải quyết (DFS):

• Xây dựng danh sách kề graph từ ma trận kề arr.
• Mảng color kích thước n khởi tạo -1 (chưa tô màu).
• result = [True].
• Định nghĩa hàm dfs(source):
  • Duyệt các đỉnh kề child của source:
    • Nếu color[child] != -1:
      • Nếu color[child] == color[source], gán result[0] = False và trả về.
      • Tiếp tục đỉnh kề tiếp theo.
    • color[child] = 1 - color[source].
    • Gọi đệ quy dfs(child).
• Với mỗi đỉnh i chưa tô màu, gọi dfs(i).
• Trả về result[0].

Ví dụ minh họa

from collections import defaultdict

class Solution:
    def solve(self, arr):
        n = len(arr)
        graph = [set() for _ 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