Python에서 방향 그래프를 반전시키는 프로그램

방향 그래프가 있다고 가정하고 그 반대 방향을 찾아야 하므로 간선이 u에서 v로 이동하면 이제 v에서 u로 이동합니다. 여기서 입력은 인접 목록이 될 것이며 n개의 노드가 있는 경우 노드는 (0, 1, ..., n-1)이 됩니다.

따라서 입력이 다음과 같으면

그러면 출력은

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ans :=n개의 서로 다른 목록의 목록, 여기서 n은 정점의 수입니다.
• 그래프의 각 인덱스 i와 인접 목록 l에 대해 다음을 수행합니다.
  • l의 각 x에 대해 다음을 수행합니다.
    • as[x] 끝에 i 삽입
• 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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

입력

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

출력

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