Chương trình kiểm tra nút chung có thể đến được trong đồ thị có hướng Python

Cho danh sách cạnh của đồ thị có hướng n nút (0 đến n-1) và hai nút a, b. Kiểm tra xem có tồn tại nút c sao cho có đường đi từ c đến a VÀ từ c đến b hay không.

Ví dụ: edges=[(0,4),(4,3),(1,2),(0,1),(0,2),(1,1)], a=2, b=3 → True (nút 0 đến được cả 2 và 3).

Giải thuật (DFS ngược)

1. Xây đồ thị ngược (cạnh từ y→x thay vì x→y)
2. Chạy DFS từ a và b trên đồ thị ngược để tìm tất cả nút có thể đến a và b
3. Kiểm tra giao của hai tập hợp có rỗng không

Ví dụ triển khai

def edge_list_to_graph(edges):
    nodes = set()
    for x, y in edges:
        nodes.add(x)
        nodes.add(y)
    n = len(nodes)
    graph = [[] for _ in range(n)]
    for x, y in edges:
        graph[y].append(x)  # Đảo chiều cạnh
    return graph

def DFS(graph, node, visited):
    if node not in visited:
        visited.add(node)
        for x in graph[node]:
            DFS(graph, x, visited)

def solve(edges, a, b):
    graph = edge_list_to_graph(edges)
    visited_a, visited_b = set(), set()
    DFS(graph, a, visited_a)
    DFS(graph, b, visited_b)
    return bool(visited_a.intersection(visited_b))

ed_list = [(0,4),(4,3),(1,2),(0,1),(0,2),(1,1)]
print(solve(ed_list, 2, 3))

Đầu vào

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

Đầu ra

True