Chương trình kiểm tra chu trình độ dài lẻ trong đồ thị vô hướng trong Python

Cho đồ thị vô hướng dưới dạng danh sách kề. Kiểm tra xem có tồn tại chu trình (cycle) độ dài lẻ hay không.

Ví dụ: adj_list = [[1,2],[0,3,4],[0,3,4],[1,2,4],[1,2,3]] → có chu trình lẻ như [1,3,4] (độ dài 3) → True.

Giải thuật (DFS phát hiện chu trình lẻ qua độ sâu)

• Duy trì visited tập nút đã thăm hoàn toàn, path ánh xạ nút → độ sâu trong DFS hiện tại.
• Hàm dfs(node, depth):
  • Nếu node trong path: chu trình phát hiện, độ dài = depth - path[node]. Trả về True nếu lẻ.
  • Nếu node trong visited: False.
  • Thêm vào visited, ghi path[node]=depth.
  • Đệ quy cho các nút kề.
  • Xóa path[node] khi backtrack.
• Gọi DFS từ mọi nút chưa thăm.

Mã nguồn Python

class Solution:
    def solve(self, arr):
        def dfs(node, depth):
            if node in path:
                return (depth - path[node]) % 2 == 1
            if node in visited:
                return False
            visited.add(node)
            path[node] = depth
            for nei in arr[node]:
                if dfs(nei, depth + 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))  # Output: True

Đầu vào

[[1, 2], [0, 3, 4], [0, 3, 4], [1, 2, 4], [1, 2, 3]]

Đầu ra

True