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

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告