Pythonで、どの都市からでも他のどの都市へも到達できるかどうかを判定するプログラム

問題概要

0から n-1 までの番号で表される n 個の都市と、ある都市から別の都市へ向かう一方通行の道路のリストが与えられます。このとき、「どの都市から出発しても、他のどの都市にも到達できるか」どうかを判定します。

たとえば、入力が n = 3、roads = [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]] の場合、出力は True になります。これは、都市0から都市1へ移動でき、都市1から都市0へも戻れるためです。

解法のアプローチ

この問題は、グラフが「強連結(strongly connected)」であるかどうかを判定する問題と同じです。以下の手順で解いていきます。

• dfs() 関数を定義します。引数は i、visited、g の3つです。

• 頂点 i を訪問済みとしてマークします。

• g[i] に含まれる各頂点 j について、まだ訪問していない場合は dfs(j, visited, g) を再帰的に呼び出します。

• travel() 関数を定義します。引数はグラフ g です。

• visited を空の集合として初期化し、dfs(0, visited, g) を呼び出します。

• visited のサイズが n と一致すれば True を返します。

• メイン処理では次を行います。

  • 順方向グラフ graph と逆方向グラフ rev_graph を空の辞書(defaultdict)として用意します。

  • roads 内の各道路 (u, v) について、graph[u] に v を追加し、rev_graph[v] に u を追加します。

• travel(graph) と travel(rev_graph) がどちらも True の場合にのみ True を返します。

順方向グラフ上で都市0から全都市に到達でき、かつ逆方向グラフ上でも同様に全都市に到達できれば、任意の2都市間で相互に行き来できることが保証されます。

実装例

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

計算量について

このアルゴリズムの時間計算量は O(n + m) です(n は都市の数、m は道路の数)。各都市と各道路を高々2回(順方向・逆方向それぞれ1回ずつ)走査するだけだからです。空間計算量も O(n + m) となり、グラフの隣接リストと訪問管理用の集合が主なメモリ使用源になります。