程序检查我们是否可以使用Python上所有课程

假设我们有一个2D矩阵，其中matrix [i]代表注册课程i所需的先修课程列表。现在，我们必须检查是否可以参加所有课程。

因此，如果输入像矩阵= [[1]，[2]，[]]，那么输出将为True，因为我们可以选择课程2，然后选择课程1，然后选择课程0。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数dfs()。这需要我

• 如果vis [i]为真，则

• 返回假

• 如果chk [i]为真，则

• 返回True

• vis [i]：=真

• 对于矩阵[i]中的每个j，

• 返回False

• 如果dfs(j)为假，则

• vis [i]：= False

• chk [i]：=真

• 返回True

• 从主要方法中，执行以下操作-

• vis：==大小与矩阵的行数相同的列表，最初都为false

• chk：=列表的大小与矩阵的行数相同，最初都为false

• 对于范围在0到矩阵行数的i，执行

• 返回False

• 如果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