---
title: "210. Course Schedule II"
url: "https://laigary.com/interview/coding/210-course-schedule-ii"
type: "note"
section: "coding"
date: "2023-01-31"
updated: "2026-08-09"
tags: ["Graph", "Topological Sort", "Breadth-First Search", "Depth-First Search", "Classic"]
---

# 210. Course Schedule II

[210. Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)

跟 [207](/interview/coding/207-course-schedule) 一樣的輸入，但不只要判斷能不能修完，還要**回傳一組合法的修課順序**；有環就回傳空陣列。

## 思路

[207](/interview/coding/207-course-schedule) 已經把圖建好、環也找出來了。前面已經想到要怎麼做之後，這裡很容易卡住有盲點：本來只是要判斷有沒有環，**那要在哪裡、怎麼記錄路徑的資訊呢？**

### 後序遍歷的順序就是修課順序

這時候我會建議把 `hasCycle` 跳出來看 —— 整個 for 迴圈其實就是一個**後序遍歷**。假設我們有一份正確的修課順序表，要把它印出來，那恰好就是後序遍歷的結果。所以只要**在完成後序遍歷的地方做紀錄**即可。

為什麼成立？回頭看 207 建圖的方向是 **`課程 → 它的先修課`**：

```python
graph[course].append(prerequisite)
```

後序的意思是「**所有孩子都處理完了才處理自己**」。在這個方向下，一門課的「孩子」就是它的先修課 —— 所以當我們把某門課 `append` 進答案時，**它的所有先修課早就已經在陣列裡了**。這正是修課順序要的性質。

### 建圖方向決定了要不要反轉

這是這題最容易踩的坑。同樣是後序 DFS，邊的方向反過來，結果也要反過來：


| 建圖方向                | 後序 append 的結果 | 要不要反轉         |
| ------------------- | ------------- | ------------- |
| `課程 → 先修課`（207 的方向） | 先修在前          | **不用**        |
| `先修課 → 課程`          | 先修在後          | **要 reverse** |


很多教科書寫的是第二種（因為那是「依賴指向被依賴者」的自然方向），所以會看到最後有一行 `return order[::-1]`。

## 解題方向

### 後序 DFS

主體跟 [207 的方法三](/interview/coding/207-course-schedule)完全一樣，只是多了一行 `order.append`：

1. 對每一門課去做回溯法
2. 如果發現了有課程會造成環，那就回傳空陣列
3. 如果跑完每一門課都沒有問題，那後序遍歷的順序就是修課的順序

```python
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = defaultdict(list)

        for course, prerequisite in prerequisites:
            graph[course].append(prerequisite)

        state = {} # 不在裡面：沒碰過；False：正在處理；True：處理完
        order = []

        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
            order.append(course)
            return False

        for course in range(numCourses):
            if hasCycle(course):
                return []

        return order
```

`order.append(course)` 放在 `state[course] = True` **後面** —— 也就是這門課被標記成「處理完」的那一刻。因為每個節點只會從「正在處理」走到「處理完」一次，所以每門課恰好被 append 一次，不會重複。

（`state` 這個字典為什麼是三個狀態、為什麼收尾是改值而不是刪 key，推導寫在 [207 的「兩個布林，其實只有三種狀態」](/interview/coding/207-course-schedule)，這裡不重複。）

### BFS

Kahn 的做法**天生就在輸出順序**，連後序都不用想 —— 從佇列彈出的先後就是答案：

```python
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:

        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)
        order = []

        while queue:
            course = queue.popleft()
            order.append(course)
            for nxt in graph[course]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        return order if len(order) == numCourses else []
```

注意這版建圖的方向是 `先修課 → 課程`，跟上面那版相反 —— 但因為它是**從入度 0 開始往外推**，出來的順序本來就是先修在前，同樣不用反轉。

`len(order) == numCourses` 一行同時完成了 207 的工作：排不完就代表有環（[為什麼排不完就一定有環](/interview/coding/207-course-schedule)）。

## 補充

**這一版的程式碼曾經多了一行 `if course in checked: return False`**，而 `checked` 從頭到尾沒有定義過，執行時會直接 `NameError`。那行也是多餘的 —— `state` 字典已經把「在不在路徑上」和「結論是什麼」都記下來了，不需要第二個集合。現在已經拿掉。

**拓撲排序的答案通常不唯一**。`[0,1,2,3]` 和 `[0,2,1,3]` 可能都對，題目說「回傳任何一組」就好。DFS 版和 Kahn 版給出的順序常常不一樣，兩個都是合法解。

**家族**：


| 題目                                                                | 變化                             |
| ----------------------------------------------------------------- | ------------------------------ |
| [207. Course Schedule](/interview/coding/207-course-schedule)     | 有沒有環                           |
| 210                                                               | 輸出一組合法順序                       |
| [269. Alien Dictionary](/interview/coding/269-alien-dictionary)   | 難在**建圖** —— 從相鄰兩個單字的第一個相異字元推出邊 |
| [1136. Parallel Courses](/interview/coding/1136-parallel-courses) | 最少幾個學期＝拓撲排序的層數，Kahn 分層最好寫      |


## 複雜度

**後序 DFS**

- 時間 $O(n + m)$ — 每門課只會被展開一次，每條先修關係只走一次
- 空間 $O(n + m)$ — 圖 $O(m)$，`state` 和遞迴堆疊各最壞 $O(n)$

**入度 ＋ BFS（Kahn）**

- 時間 $O(n + m)$ — 建圖和入度掃過 $m$ 條關係，之後每門課進出佇列一次、每條邊被減一次
- 空間 $O(n + m)$ — 圖 $O(m)$，`indegree` 和佇列各 $O(n)$；沒有遞迴堆疊

其中 $n$ 是課程數，$m$ 是先修關係的數量。輸出的 `order` 是 $O(n)$，不計入額外空間。