HTML CSS JAVASCRIPT JQUERY AI PHP SQL EXCEL LINUX C# C++ C PYTHON JAVA 教程库 参考手册 技术文章 测验 练习 HOWTO FAQ

用 Python 编写程序检查是否可以选修所有课程

pythonserver side programmingprogramming更新于 2026/1/12 9:16:17

假设我们有一个 2D 矩阵，其中 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，则

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

相关文章

有用资源

打印 下一节:用 Python 编写程序检查字符串的两个部分是否为回文 ❯❮ 上一节:用 Python 编写程序查找第一个值和最后一个值相同的子列表