--- title: "207. Course Schedule" url: "https://laigary.com/interview/coding/207-course-schedule" type: "note" section: "coding" date: "2023-01-29" updated: "2026-08-09" tags: ["Graph", "Topological Sort", "Breadth-First Search", "Depth-First Search", "Classic"] --- # 207. Course Schedule [207. Course Schedule](https://leetcode.com/problems/course-schedule/) 給 `numCourses` 門課和一組 `[課程, 先修課]` 的關係，問所有課能不能修完。 這一個題目的設計滿巧妙的，我個人覺得它綜合了**樹的遍歷（遞迴）、回溯法、動態規劃以及資料與圖形轉換**的設計，外加上題目可以套用在各種現實生活問題中。所以整體而言 LeetCode 給出了中等難度，但是細節很多很需要小心的想通。 而且我不得不承認，每次我在複習這個題目的時候，都還是要花點時間去推敲整個題目的細節。 ## 思路 其實這個題目滿貼近大學時的生活的，那就是很多科目都有擋修，那系上設計這個課程的時候，不能怎麼樣設計？舉例來說：系上的課程不能說這樣，要修過計算機概論才能修演算法，要修過演算法要才能資料結構，然後要修過資料結構才能修計算機概論，這就充滿了邏輯的矛盾，這個題目就是要看有沒有這種矛盾。 **目標於是很明確：這個課程的前後關係，會不會造成環。** 有環代表「A 要先修 B、B 要先修 C、C 又要先修 A」，永遠開不了頭。 ### 「走過」和「有環」不是同一件事 這是這題最容易錯的地方。走訪時遇到一個看過的節點，**不代表有環**： ```text 0 / \ 1 2 \ / 3 ``` 從 0 出發，走 0→1→3 之後回頭走 0→2→3，會第二次遇到 3 —— 但這張圖沒有環。 **只有遇到「還在目前這條路徑上」的節點，才是環。** ### 先把資料轉成圖 課程和先修課的關係本身就是一張**有向圖**：把每門課當成一個節點，「A 的先修課是 B」就是一條 A 指向 B 的邊。 （原本我把它想成「一棵或很多棵樹」，那個直覺方向是對的，但嚴格說它是圖不是樹 —— 一門課可以同時是很多門課的先修課，也就是一個節點可以有多個「父親」。真正的差別在於**圖可能有環，樹不會**，而這題要找的就是環。） 題目給的是一個沒有特定排列順序的數列，如同其他很多圖的題目，第一步先建立整個圖。但是在這裡，我們其實就會有第一個要討論的地方，那就是我們透過 Hash Table 這個資料結構時，方向有沒有關係？ - 課程 → 所有先修課 - 先修課 → 所有被擋修的課程 這邊我想要先把 [210. Course Schedule II](/interview/coding/210-course-schedule-ii) 稍微拿出來討論一下，這兩個題目的差別就在於是否要給出修課的路徑。 其實如果我們把上面的例子稍微看一下，就會發現其實兩個方向都是可以的，我們從哪個方向去檢查，只要沒有環就可以了（下面兩個迴圈是二選一，不是兩個都建） ```python graph = defaultdict(list) # 課程 → 所有先修課 for course, prerequisite in prerequisites: graph[course].append(prerequisite) # 先修課 → 所有被擋修的課程 for course, prerequisite in prerequisites: graph[prerequisite].append(course) ``` （這個結論只在「只要判斷有沒有環」的前提下成立。等一下寫到 BFS 的時候會發現，換一個問法之後方向就被鎖死了。） ### 那到底要選什麼演算法？ 這裡其實大概就可以想到要使用 [BFS / DFS](/interview/coding/bfs-dfs-template) 來解題了，因為我們就要開始遍歷這個圖，這裡也是比較困難的細節要處理。 我們可以用一個圖去思考，在做單純的 BFS / DFS 的時候，我們通常會去記錄已經造訪過的節點，在下方的圖片，我如果從 0 開始出發走過一個路徑 `0 → 1 → 2 → 4`，這時候 1 已經造訪過了，但是我們不能把它標記成不能再次造訪，因為如果這樣的話，我們就沒辦法檢查 `0 → 1 → 3 → 4` 這個路徑了，所以這也是如果我們要使用 BFS / DFS 時要注意的地方。 寫到這邊，其實我就會開始選擇使用 DFS 因為展開後其實就是 [Backtracking](/interview/coding/backtracking-template) 的做法，我會在後面繼續討論 BFS 的想法是什麼。 ``` 0 \ 1 / \ 2 3 \ / 4 ``` ## 解題方向 ### 方法一：回溯法（超時） 透過最後的 for 迴圈，我們要檢查每一門課，看它底下是否有環。 ```python class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = defaultdict(list) for course, prerequisite in prerequisites: graph[course].append(prerequisite) def hasCycle(course, on_path): if course in on_path: return True on_path.add(course) for child in graph[course]: if hasCycle(child, on_path): return True on_path.remove(course) return False for course in range(numCourses): if hasCycle(course, set()): return False return True ``` **這個集合原本我命名成 `visited`，但那個名字會誤導** —— 它裝的不是「造訪過的節點」，而是「**目前這條路徑上的節點**」，所以改叫 `on_path`。 #### 那個 `if course in on_path: return True` 為什麼成立 因為結尾有 `on_path.remove(course)`。**進入時加、離開時移除**，所以在任何時刻，`on_path` 裝的剛好就是「從起點走到我現在位置」的那條路徑 —— 它是遞迴堆疊的鏡子。 既然 `on_path` = 目前這條路，那「走到一個已經在裡面的節點」就是說：**有一條路從它出發，繞了一圈又回到它自己**。那就是環。 有環的時候（`0` 需要 `1`、`1` 需要 `2`、`2` 需要 `0`）： ```text 進入 0，on_path = [] 進入 1，on_path = [0] 進入 2，on_path = [0, 1] 進入 0，on_path = [0, 1, 2] → 0 已經在裡面 → True ``` 沒有環的時候（上面那張菱形圖），`remove` 的作用就看出來了： ```text 進入 0，on_path = [] 進入 1，on_path = [0] 進入 3，on_path = [0, 1] 離開 3，移除後 on_path = [0, 1] 離開 1，移除後 on_path = [0] 進入 2，on_path = [0] ← 1 和 3 都已經被移掉 進入 3，on_path = [0, 2] ← 3 不在裡面，正常展開 ``` **如果把 `remove` 拿掉**，第二次走到 3 就會被誤判成環： ```text 進入 2，on_path = [0, 1, 3] ← 1 和 3 還留著 進入 3，on_path = [0, 1, 2, 3] → 3 已經在裡面 → True ← 誤判 ``` 所以 `if ... return True` 和 `remove` 是一組的，缺一個就錯。**`remove` 是讓那個 `return True` 成立的前提。** #### 為什麼會超時 題目的範例都沒有問題，但是這樣的方法會超時。因為如果有 $n$ 門課程，相當於我們要遍歷這麼多棵樹；如果說第 $i$ 門課有先修課 $k$，那這樣的方法就會在探索時，再次檢查第 $k$ 門課是不是有環的存在。**有點像是動態規劃的子問題 —— 同一個子問題被重算了很多次。** ### 方法二：回溯法＋記憶 方法一會超時的原因是，我們不斷地去檢查已經檢查過的課程。更好的方法是：**當一門課確定底下沒有環之後，就把這個結論記起來**，下次直接用。 ```python class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = defaultdict(list) for course, prerequisite in prerequisites: graph[course].append(prerequisite) memo = [False] * numCourses # 這門課底下已經確認沒有環 def hasCycle(course, on_path): if course in on_path: return True if memo[course]: return False on_path.add(course) for child in graph[course]: if hasCycle(child, on_path): return True on_path.remove(course) memo[course] = True # 底下確定沒有環 return False for course in range(numCourses): if hasCycle(course, set()): return False return True ``` `memo` 在這裡記錄的是「這門課底下已經確認沒有環」，所以當我再次看到 `k` 課程時，我不用再去遍歷一次所有的路徑，上面是做了類似動態規劃的記憶法，去記憶已經驗證過的的課程，**時間複雜度也變成線性**。 我的筆記算是紀錄從面試作答，到怎麼樣在面試中慢慢走到現在這一步，取決於面試所剩下的時間，面試官可能會覺得這樣就好了。但是這裡有一個可以優化的地方，那就是我們能不能再去簡化記憶的這個過程？ 這會是一個更難的 follow up 問題，所以我們要分析這件事情，那就是當我們進入到一個節點（課程）的時候，需要注意什麼？這裡會需要從我們當前的最後一個答案開始分析回去。 #### 兩個布林，其實只有三種狀態 我一開始想不到「用一個結構管三種狀態」，是因為我直接去想答案長什麼樣子。**應該反過來：先老實地把方法二進入一個節點時問過的問題列出來，再去看這些問題彼此的關係。** ```python def hasCycle(course, on_path): if course in on_path: # 問題一 return True if memo[course]: # 問題二 return False ``` 兩個布林問題，攤開來是四種組合： | `course in on_path` | `memo[course]` | 代表什麼 | | ------------------- | -------------- | ------------ | | True | False | 在目前這條路上 → 有環 | | False | True | 已經確認底下沒有環 | | False | False | 沒碰過，要展開 | | True | True | 不會發生 | 第四種永遠不會發生，而且原因就寫在程式碼的順序裡：`memo[course] = True` 這一行在 `on_path.remove(course)` 的**後面**。一個節點是先離開路徑，才被標記成完成的，所以它不可能同時「還在路上」又「已經完成」。 **四種組合只用到三種，那就不是兩個獨立的旗標，而是一個有三個值的狀態被我拆成了兩個變數。** 這個判斷方式可以直接帶去別題：只要幾個布林值之間互相排斥、組合數用不滿，通常就是同一個狀態被拆開了。 而且這三種不是隨便三種，它剛好就是一個節點在 DFS 裡的**生命週期**： ```text 沒碰過 → 正在處理（在目前這條路徑上） → 處理完（底下確定沒有環） ``` 生命週期是單向的，不會倒退。這一點回頭解釋了 `remove`：在方法二裡它看起來像是「把節點放回沒碰過」，但它後面緊接著 `memo[course] = True`，兩行加起來才是一個完整的動作 —— **離開路徑，然後往前走到「處理完」**。我需要寫成兩行，只是因為我用兩個結構去存一件事。 接下來就是把這三個狀態寫成一個結構，看看程式碼會少掉哪些東西。 ### 方法三：一個 `state` 管三個狀態 不要叫 `visited`，那個名字在這篇已經害我一次了。叫 `state`，因為它回答的是「這個節點現在在哪個階段」，不是「有沒有看過」。 #### 寫法一：用 dict key 在不在代表「有沒有碰過」，value 的布林代表碰過之後的那兩個狀態。 ```python class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = defaultdict(list) for course, prerequisite in prerequisites: graph[course].append(prerequisite) state = {} # 不在裡面：沒碰過；False：正在處理；True：處理完 def hasCycle(course): if state.get(course) is False: # 正在處理 → 有環 return True if state.get(course) is True: # 處理完 return False state[course] = False for child in graph[course]: if hasCycle(child): return True state[course] = True return False for course in range(numCourses): if hasCycle(course): return False return True ``` 這裡要用 `is` 而不是直接判斷真假值，因為沒碰過時 `get` 回傳的是 `None`，而 `None` 和 `False` 都是 falsy，直接寫 `if not state.get(course)` 會把「沒碰過」也當成「正在處理」。 收尾是 `state[course] = True`，**不是 `del state[course]`**。刪掉 key 等於把它退回「沒碰過」，記憶就沒了，會退回方法一的超時。刪掉還是改值，就是方法一和方法三的差別。 #### 寫法二：用陣列 這題的節點剛好是 `0` 到 `numCourses - 1` 的密集整數，所以直接開一個等長的陣列，三個狀態就用三個數字。dict 的價值在節點是字串或稀疏 id 的時候。 ```python class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = defaultdict(list) for course, prerequisite in prerequisites: graph[course].append(prerequisite) UNVISITED, VISITING, DONE = 0, 1, 2 state = [UNVISITED] * numCourses def hasCycle(course): if state[course] == VISITING: return True if state[course] == DONE: return False state[course] = VISITING for child in graph[course]: if hasCycle(child): return True state[course] = DONE return False for course in range(numCourses): if hasCycle(course): return False return True ``` #### 一份 `state` 共用會不會互相汙染？ 方法二的 `on_path` 是**每條路徑各自一份**，外圈每跑一次就給一個新的 `set()`；方法三的 `state` 是**整份共用**，跨外圈的每一輪都留著。直覺上這應該要出事才對。 但它不會，因為 `VISITING` 只存在於遞迴展開的期間。**外圈跑到下一輪時，上一輪的遞迴已經全部結束了**，所以那時候 `state` 裡只剩 `UNVISITED` 和 `DONE`，不可能有殘留的 `VISITING` 去誤導下一輪。 留下來的 `DONE` 也正是我們要的 —— 那就是方法二的 `memo`。 ### 方法四：BFS 前面提到的 BFS 在這裡，其實用想像的方式去看 BFS 好像還是可以解得出題目，但是實作上卻很困難，尤其是如果把 DFS 的找環的方式來 BFS 做，可能會讓面試時失敗，DFS 問的是：**這門課往下追它的先修課，會不會繞回它自己？** **BFS** 我必須承認我想不出來，是後來看解答才想到的。 - BFS 問的是：**現在有哪些課是馬上就能修的？修完它之後，又解鎖了哪些課？** 順著第二個問法往下想，需要的東西就一個一個掉出來了： 1. 「馬上就能修」代表**它沒有任何還沒修完的先修課**。所以我要能查一門課還欠幾門先修課，那就開一個 `indegree` 陣列來記。 2. 「修完 A 之後解鎖了誰」代表我要能從 A 查到**被 A 擋住的課**。這一步就把圖的方向鎖死成 `先修課 → 課程`。 3. 解鎖的動作就是把那些課的 `indegree` 減一，減到 0 就代表它可以修了，丟進佇列。 4. 佇列空掉的時候推不動了，這時候看**修完的課數有沒有等於 `numCourses`**。207 要的就只是這個布林。 ```python class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = defaultdict(list) indegree = [0] * numCourses for course, prerequisite in prerequisites: graph[prerequisite].append(course) indegree[course] += 1 queue = deque(course for course in range(numCourses) if indegree[course] == 0) finished = 0 while queue: course = queue.popleft() finished += 1 for nxt in graph[course]: indegree[nxt] -= 1 if indegree[nxt] == 0: queue.append(nxt) return finished == numCourses ``` 這一版完全沒有遞迴，也沒有「還在不在路徑上」這個概念 —— 因為它根本不走路徑。 #### 為什麼「排不完的那些課一定在環裡」 這是這個解法唯一需要證明的地方，也是面試時要能講出口的一句。 假設某門課 X 到最後都沒有被彈出佇列，那代表 **X 的 `indegree` 從頭到尾沒有歸零**，也就是至少有一門先修課 Y 也沒有被修到。同樣的道理套在 Y 身上，Y 也一定有一門沒被修到的先修課 Z⋯⋯ 這條「每一門都還有前一門」的鏈可以無限往前追，但課程總數是有限的，所以**一定會追到某一門重複出現**。重複出現就是繞回來了，那就是環。 反過來也成立：如果沒有環，每一輪一定至少有一門課的入度是 0（否則就會出現上面那條無限鏈），所以佇列不會提前空掉，最後 `finished` 一定等於 `numCourses`。 #### 回頭看「方向到底有沒有關係」 前面建圖的時候我說兩個方向都可以，那句話**只在「判斷有沒有環」的前提下成立** —— DFS 從哪一頭走都會踩到同一個環。 但問法一換成「解鎖」，方向就沒得選了： | 我要問的事 | 圖的方向 | | --------------------------------------------------------- | ------------- | | 有沒有環（DFS） | 兩個方向都行 | | 現在能修哪些課、修完解鎖誰（Kahn） | 只能 `先修課 → 課程` | | 輸出一組修課順序（[210](/interview/coding/210-course-schedule-ii)） | 方向決定要不要反轉結果 | 所以這題的四個解法裡，前三個用 `課程 → 先修課`，只有 Kahn 這版反過來。**不是我隨便換的，是問法逼出來的。** ## 複雜度 **方法一：回溯法** - 時間 $O(2^n)$ — 每門課都要重新列舉它底下的所有路徑，而路徑數最壞會隨課程數指數成長 - 空間 $O(n + m)$ — 圖佔 $O(m)$，遞迴堆疊和 `on_path` 最深 $O(n)$ **方法二：回溯法＋記憶** - 時間 $O(n + m)$ — 每門課只會真的被展開一次，之後都被 `memo` 擋掉；每條先修關係只走一次 - 空間 $O(n + m)$ — 圖 $O(m)$，`memo`、`on_path` 和遞迴堆疊各 $O(n)$ **方法三：三個狀態** - 時間 $O(n + m)$ — 跟方法二一樣，每個節點的狀態只會單向從 `UNVISITED` 走到 `DONE` - 空間 $O(n + m)$ — 一樣，但少一個結構：`on_path` 和 `memo` 併成一個 `state` **方法四：入度 ＋ BFS** - 時間 $O(n + m)$ — 建圖和入度掃過 $m$ 條關係，之後每門課進出佇列一次、每條邊被減一次 - 空間 $O(n + m)$ — 圖 $O(m)$，`indegree` 和佇列各 $O(n)$；沒有遞迴堆疊 其中 $n$ 是課程數，$m$ 是先修關係的數量。