假设我们有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