Chương trình kiểm tra có thể đi từ bất kỳ thành phố nào đến thành phố khác không trong Python

Cho n thành phố (0..n-1) và danh sách đường một chiều roads. Kiểm tra xem có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác không (đồ thị liên thông mạnh).

Ví dụ

Đầu vào: n=3, roads=[[0,1],[0,2],[1,0],[1,2],[2,0],[2,1]].
Đầu ra: True.

Thuật toán

1. Xây dựng đồ thị graph và đồ thị ngược rev_graph.
2. Hàm dfs đánh dấu visited.
3. Hàm travel(g): DFS từ đỉnh 0, kiểm tra visited có đủ n đỉnh không.
4. Trả về travel(graph) and travel(rev_graph).

Mã nguồn Python

class Solution:
    def solve(self, n, roads):
        from collections import defaultdict
        graph = defaultdict(list)
        rev_graph = defaultdict(list)
        for u, v in roads:
            graph[u].append(v)
            rev_graph[v].append(u)
        def dfs(i, visited, g):
            visited.add(i)
            for j in g[i]:
                if j not in visited:
                    dfs(j, visited, g)
        def travel(g):
            visited = set()
            dfs(0, visited, g)
            return len(visited) == n
        return travel(graph) and travel(rev_graph)

ob = Solution()
n = 3
roads = [[0,1],[0,2],[1,0],[1,2],[2,0],[2,1]]
print(ob.solve(n, roads))

Đầu vào / Đầu ra

Input: 3, [[0,1],[0,2],[1,0],[1,2],[2,0],[2,1]]
Output: True