程序检查我们是否可以使用Python来访问来自任何城市的任何城市

  • Z时代
  • 2024-01-10
  • 分类：综合

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

因此，如果输入像n = 3，则道路= [[0，1]，[0，2]，[1,0]，[1,2]，[2,0]，[2,1]] ，那么输出将为True，因为您可以将0设为1，并将1设为0

为了解决这个问题，我们将按照以下步骤操作：

  • 定义一个功能dfs()。这将需要我访问过的g

  • 将我标记为已访问

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

    • dfs（j，已访问，g）

    • 如果没有访问j，则

    • 定义一个功能travel()。这将花费g

    • 参观了：=一套新的

    • dfs（0，已访问，g）

    • 当访问的大小与n相同时，返回true

    • 从主要方法，请执行以下操作-

    • 图：=一个空的映射

    • rev_graph：=一个空的映射

    • 对于道路上的每个来源u和目的地v，

      • 在图形的末尾插入v [u]

      • 在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

    以上是 程序检查我们是否可以使用Python来访问来自任何城市的任何城市 的全部内容， 来源链接： utcz.com/z/331257.html

    回到顶部