Pythonで、どの都市からでも、どの都市からでも訪問できるかどうかを確認するプログラム

範囲[0、n）の数値として表されたn個の都市があり、ある都市を別の都市に接続する一方通行の道路のリストもあるとします。どの都市からどの都市にも到達できるかどうかを確認する必要があります。

したがって、入力がn =3の場合、roads =[[0、1]、[0、2]、[1,0]、[1,2]、[2,0]、[2,1]] 、0から1および1から0に移動できるため、出力はTrueになります

これを解決するために、次の手順に従います-

• 関数dfs（）を定義します。これには、i、visited、g

  が必要です。

• iを訪問済みとしてマーク

• g [i]のjごとに、実行

  • jにアクセスしない場合は、

    • dfs（j、visited、g）

• 関数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