Chương trình đảo ngược đồ thị có hướng bằng Python

Cho một đồ thị có hướng dưới dạng danh sách kề, hãy tìm đồ thị đảo ngược: nếu cạnh đi từ u đến v, cạnh mới đi từ v đến u. Các nút được đánh số từ 0 đến n-1.

Quy trình giải quyết

1. Khởi tạo danh sách kết quả ans chứa n danh sách rỗng.
2. Duyệt qua từng nút i và danh sách kề l của nó.
3. Với mỗi x trong l, thêm i vào ans[x].
4. Trả về ans.

Ví dụ mã nguồn

class Solution:
    def solve(self, graph):
        ans = [[] for _ in graph]
        for i, l in enumerate(graph):
            for x in l:
                ans[x].append(i)
        return ans

ob = Solution()
graph = [[1,2], [4], [4], [1,2], [3]]
print(ob.solve(graph))
# Output: [[], [0, 3], [0, 3], [4], [1, 2]]

Đầu vào

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

Đầu ra

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