用 Python 编写的反转有向图的程序

pythonserver side programmingprogramming更新于 2026/2/3 7:08:17

假设我们有一个有向图，我们必须找到它的反转，因此如果一条边从 u 到 v，那么它现在从 v 到 u。此处的输入将是一个邻接列表，如果有 n 个节点，则节点将为 (0, 1, ..., n-1)。

因此，如果输入如下

则输出将是

为了解决这个问题，我们将遵循以下步骤 −

ans := n 个不同元素的列表列表，其中 n 是顶点数
对于图中的每个索引 i 和相邻列表 l，执行
- 对于 l 中的每个 x，执行
  - 将 i 插入 ans[x] 末尾
返回 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))