Pythonですべてのコースを受講できるかどうかを判定するプログラム

2次元の行列が与えられ、matrix[i] にはコース i を受講するために必要な前提コース（履修条件）のリストが格納されているものとします。このとき、すべてのコースを受講することが可能かどうかを判定する必要があります。

例えば、入力が matrix = [[1],[2],[]] の場合、出力は True になります。これは、コース 2 → コース 1 → コース 0 の順番で受講できるためです。

この問題は、前提関係を有向グラフとみなし、深さ優先探索（DFS）によってサイクル（循環参照）が存在しないかを確認することで解けます。前提コース同士が循環していると、その環状の中にあるコースはどれも受講できず、結果としてすべてのコースの修了は不可能になります。

アルゴリズムの手順

まず、dfs(i) という関数を定義します。この関数は次のように動作します。

• vis[i] が True の場合（現在の探索経路上で既に訪問済み＝サイクルを検出）、False を返します。
• chk[i] が True の場合（過去の探索で問題ないことが確認済み）、True を返します。
• vis[i] := True と設定します。
• matrix[i] 内の各要素 j について、dfs(j) が False を返したら、False を返します。
• vis[i] := False に戻し（バックトラック）、chk[i] := True として True を返します。

続いて、メイン処理では以下を行います。

• vis：matrix の行数と同じサイズのリストで、初期値はすべて False。現在の探索パス上の訪問状態を管理します。
• chk：matrix の行数と同じサイズのリストで、初期値はすべて False。一度確認が完了したノードを記録し、再計算を避けるメモ化の役割を果たします。
• i を 0 から matrix の行数まで順にループし、dfs(i) が False を返したら False を返します。
• すべての i で dfs(i) が成功すれば、True を返します。

それでは、理解を深めるために実際の実装を見てみましょう。

実装例

class Solution:
   def solve(self, matrix):
      vis=[False for _ in matrix]
      chk=[False for _ in matrix]
      def dfs(i):
         if vis[i]: return False
         if chk[i]: return True
         vis[i]=True
         for j in matrix[i]:
            if not dfs(j):
               return False
         vis[i]=False
         chk[i]=True
         return True
   for i in range(len(matrix)):
      if not dfs(i):
         return False
   return True
ob = Solution()
matrix = [ [1], [2], [] ]
print(ob.solve(matrix))

入力

matrix = [
   [1],
   [2],
   []
]

出力

True

このように、vis 配列で現在の探索経路を追跡しながらサイクルを検出し、chk 配列で確認済みのノードを記録することで、効率よくすべてのコースが受講可能かどうかを判定できます。計算量は O(V + E)（V はコース数、E は前提関係の数）となり、大規模なデータにも対応できます。