用 Python 编写程序检查我们能否从任意城市访问任意城市
pythonserver side programmingprogramming更新于 2026/1/10 14:04:17
假设我们有 n 个城市，用 [0, n) 范围内的数字表示，并且我们还有一个连接一个城市到另一个城市的单行道列表。我们必须检查我们是否可以从任意城市到达任意城市。
因此，如果输入为 n = 3，道路 = [[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, visits, g)
定义一个函数 travel() 。这将需要 g
visited := 一个新集合
dfs(0, visited, g)
当 accessed 的大小与 n 相同时返回 true
从主方法，执行以下操作−
graph := 一个空地图
rev_graph := 一个空地图
对于 roads 中的每个源 u 和目的地 v，执行以下操作
在 graph[u] 的末尾插入 v
在 rev_graph[v] 的末尾插入 u
当 travel(graph) 和 travel(rev_graph) 都为 true 时返回 true真
让我们看看下面的实现以便更好地理解 −
Example
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 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
