Python程序：检查是否可以从任何城市到达任何其他城市

假设我们有n个城市，用[0, n)范围内的数字表示，我们还有一个单向道路列表，连接一个城市到另一个城市。我们必须检查是否可以从任何城市到达任何其他城市。

因此，如果输入类似于n = 3，roads = [[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]]，则输出为True，因为您可以从0到1，从1到0。

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

  • 定义一个函数dfs()。它将接收i、visited和g。

  • 将i标记为已访问。

  • 对于g[i]中的每个j，执行：

    • 如果j未被访问，则

      • dfs(j, visited, g)

  • 定义一个函数travel()。它将接收g。

  • visited := 一个新的集合

  • dfs(0, visited, g)

  • 当visited的大小与n相同时返回true

  • 在主方法中，执行以下操作：

  • graph := 一个空映射

  • rev_graph := 一个空映射

  • 对于roads中的每个源u和目标v，执行：

    • 在graph[u]的末尾插入v

    • 在rev_graph[v]的末尾插入u

  • 当travel(graph)和travel(rev_graph)都为true时返回true

让我们看看下面的实现以更好地理解：

示例

在线演示

class Solution:
   def solve(self, n, roads):
      from collections import defaultdict
         graph = defaultdict(list)
         rev_graph = defaultdict(list)
   for u, v in roads:
      graph[u].append(v)
      rev_graph[v].append(u)
      def dfs(i, visited, g):
      visited.add(i)
   for j in g[i]:
      if j not in visited:
         dfs(j, visited,g)
         def travel(g):
         visited = set()
         dfs(0, visited, g)
      return len(visited)==n
   return travel(graph) and travel(rev_graph)
ob = Solution()
n = 3
roads = [[0, 1],[0, 2],[1,0],[1,2],[2,0],[2,1]]
print(ob.solve(n, roads))

输入

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

输出

True

更新于：2020年10月5日

733 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告