Python 程序：检查能否选修所有课程

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

因此，如果输入类似于 matrix = [[1],[2],[]]，则输出为 True，因为我们可以先修课程 2，然后是课程 1，最后是课程 0。

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

  • 定义一个函数 dfs()。这将接收 i 作为参数。

  • 如果 vis[i] 为真，则

    • 返回 false

  • 如果 chk[i] 为真，则

    • 返回 True

  • vis[i]:= True

  • 对于 matrix[i] 中的每个 j，执行以下操作：

    • 如果 dfs(j) 为假，则

      • 返回 False

  • vis[i]:= False

  • chk[i]:= True

  • 返回 True

  • 在主方法中，执行以下操作：

  • vis:= 一个大小与矩阵行数相同的列表，初始值均为 false

  • chk:= 一个大小与矩阵行数相同的列表，初始值均为 false

  • 对于从 0 到矩阵行数的 i，执行以下操作：

    • 如果 dfs(i) 为假，则

      • 返回 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

更新于：2020年10月7日

浏览量：129

开启您的职业生涯

完成课程获得认证

开始学习
广告