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

2Dマトリックスがあり、matrix[i]がコースiの登録に必要な前提条件コースのリストを表しているとします。ここで、すべてのコースを受講できるかどうかを確認する必要があります。

したがって、入力がmatrix =[[1]、[2]、[]]のような場合、コース2、コース1、コース0の順に進むことができるため、出力はTrueになります。

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

• 関数dfs（）を定義します。これには私がかかります

• vis [i]がtrueの場合、

  • falseを返す

• chk [i]が真の場合、

  • Trueを返す

• vis [i]：=True

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

  • dfs（j）がfalseの場合、

    • Falseを返す

• vis [i]：=False

• chk [i]：=True

• Trueを返す

• メインの方法から、次のようにします-

• vis：=行列の行数と同じサイズのリストで、最初はすべてfalse

• chk：=行列の行数と同じサイズのリストで、最初はすべてfalse

• 0から行列の行数までの範囲のiについては、次のようにします

  • dfs（i）がfalseの場合、

    • Falseを返す

• 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