用 Python 反轉有向圖的程式

假設我們有一個有向圖，我們需要找到它的逆圖，也就是說，如果一條邊從 u 指向 v，那麼現在它從 v 指向 u。這裡的輸入將是鄰接表，如果有 n 個節點，那麼節點將是 (0, 1, ..., n-1)。

所以，如果輸入如下

那麼輸出將是

要解決這個問題，我們將按照以下步驟進行 −

  • ans := 一個包含 n 個不同列表的列表，其中 n 是頂點的數量
  • 對於圖中的每個索引 i 和鄰接列表 l，執行
    • 對於列表中的每個 x，執行
      • 在 ans[x] 的末尾插入 i
  • 返回 ans

讓我們看看以下實現來加深理解 −

示例

 線上演示

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

更新於：20-Oct-2020

1000+ 瀏覽

開啟你的職業生涯

完成課程即可獲得認證

開始學習
廣告