你這個學期必須選修 numCourse 門課程，記為 0 到 numCourse-1 。

在選修某些課程之前需要一些先修課程。 例如，想要學習課程 0 ，你需要先完成課程 1 ，我們用一個匹配來表示他們：[0,1]

給定課程總量以及它們的先決條件，請你判斷是否可能完成所有課程的學習？

示例 1:

輸入: 2, [[1,0]]
輸出: true
解釋: 總共有 2 門課程。學習課程 1 之前，你需要完成課程 0。所以這是可能的。

示例 2:

輸入: 2, [[1,0],[0,1]]
輸出: false
解釋: 總共有 2 門課程。學習課程 1 之前，你需要先完成?課程 0；并且學習課程 0 之前，你還應先完成課程 1。這是不可能的。

提示：

輸入的先決條件是由 邊緣列表 表示的圖形，而不是 鄰接矩陣 。

你可以假定輸入的先決條件中沒有重復的邊。

1 <= numCourses <= 10⁵

深度優先搜索

給定一個包含 n 個節點的有向圖 G，給出它的節點編號的一種排列，如果滿足：**對于圖 G 中的任意一條有向邊 (u, v)，u 在排列中都出現在 v 的前面。**那么稱該排列是圖 G 的「拓撲排序」。

將本題建模成一個求拓撲排序的問題：

• 將每一門課看成一個節點；
• 想要學習課程 A 之前必須完成課程 B，那么我們從 B 到 A 連接一條有向邊。這樣以來，在拓撲排序中，B 一定出現在 A 的前面。

將深度優先搜索的流程與拓撲排序的求解聯系起來，用一個棧來存儲所有已經搜索完成的節點。

對于一個節點 u，如果它的所有相鄰節點都已經搜索完成，那么在搜索回溯到 u 的時候，u 本身也會變成一個已經搜索完成的節點。這里的「相鄰節點」指的是從 u 出發通過一條有向邊可以到達的所有節點。

假設我們當前搜索到了節點 u，如果它的所有相鄰節點都已經搜索完成，那么這些節點都已經在棧中了，此時我們就可以把 u 入棧?？梢园l現，如果我們從棧頂往棧底的順序看，由于 u 處于棧頂的位置，那么 u 出現在所有 u 的相鄰節點的前面。因此對于 u 這個節點而言，它是滿足拓撲排序的要求的。

這樣以來，我們對圖進行一遍深度優先搜索。當每個節點進行回溯的時候，我們把該節點放入棧中。最終從棧頂到棧底的序列就是一種拓撲排序。

對于圖中的任意一個節點，它在搜索的過程中有三種狀態，即：

• 「未搜索」：我們還沒有搜索到這個節點；
• 「搜索中」：我們搜索過這個節點，但還沒有回溯到該節點，即該節點還沒有入棧，還有相鄰的節點沒有搜索完成；
• 「已完成」：我們搜索過并且回溯過這個節點，即該節點已經入棧，并且所有該節點的相鄰節點都出現在棧的更底部的位置，滿足拓撲排序的要求。

通過上述的三種狀態，我們就可以給出使用深度優先搜索得到拓撲排序的算法流程，在每一輪的搜索搜索開始時，我們任取一個「未搜索」的節點開始進行深度優先搜索。

• 我們將當前搜索的節點 u 標記為「搜索中」，遍歷該節點的每一個相鄰節點 v：
  • 如果 v 為「未搜索」，那么我們開始搜索 v，待搜索完成回溯到 u；
  • 如果 v 為「搜索中」，那么我們就找到了圖中的一個環，因此是不存在拓撲排序的；
  • 如果 v 為「已完成」，那么說明 v 已經在棧中了，而 u 還不在棧中，因此 u 無論何時入棧都不會影響到 (u, v) 之前的拓撲關系，以及不用進行任何操作。
• 當 u 的所有相鄰節點都為「已完成」時，我們將 u 放入棧中，并將其標記為「已完成」。

在整個深度優先搜索的過程結束后，如果我們沒有找到圖中的環，那么棧中存儲這所有的 nn 個節點，從棧頂到棧底的順序即為一種拓撲排序。

由于我們只需要判斷是否存在一種拓撲排序，而棧的作用僅僅是存放最終的拓撲排序結果，因此我們可以只記錄每個節點的狀態，而省去對應的棧。

Code

def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:def dfs(u: int):nonlocal validvisited[u] = 1for v in edges[u]:if visited[v] == 0:dfs(v)if not valid:returnelif visited[v] == 1:valid = Falsereturnvisited[u] = 2result.append(u)edges = collections.defaultdict(list)visited, result, valid = [0] * numCourses, list(), Truefor info in prerequisites:edges[info[1]].append(info[0])for i in range(numCourses):if valid and not visited[i]:dfs(i)return valid

復雜度分析

時間復雜度: O(n+m)，其中 n 為課程數，m 為先修課程的要求數。這其實就是對圖進行深度優先搜索的時間復雜度。

空間復雜度: O(n+m)。題目中是以列表形式給出的先修課程關系，為了對圖進行深度優先搜索，我們需要存儲成鄰接表的形式，空間復雜度為 O(n+m)。在深度優先搜索的過程中，我們需要最多 O(n) 的?？臻g（遞歸）進行深度優先搜索，因此總空間復雜度為 O(n+m)。

總結

以上是生活随笔為你收集整理的207. Course Schedule 课程表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。