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

Giả sử chúng ta có một đồ thị có hướng, chúng ta phải tìm ngược lại của nó để nếu một cạnh đi từ u đến v, thì bây giờ nó sẽ đi từ v sang u. Ở đây đầu vào sẽ là một danh sách kề, và nếu có n nút, các nút sẽ là (0, 1, ..., n-1).

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ans:=một danh sách gồm n danh sách khác nhau, trong đó n là số đỉnh
• đối với mỗi chỉ mục i và danh sách liền kề l trong biểu đồ, hãy thực hiện
  • với mỗi x trong l, thực hiện
    • chèn i vào cuối ans [x]
• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

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