---
title: "1136. Parallel Courses"
url: "https://laigary.com/interview/coding/1136-parallel-courses"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-30"
tags: ["Graph", "Topological Sort", "Breadth-First Search", "Dynamic Programming", "Depth-First Search"]
---

# 1136. Parallel Courses

[1136\. Parallel Courses](https://leetcode.com/problems/parallel-courses/)

給 `n` 門課（編號 **1 到 n**）和一組先修關係，**同一個學期可以修任意多門沒有先修衝突的課**。問最少幾個學期修完，修不完回傳 -1。

這個題目是 [207. Course Schedule](/interview/coding/207-course-schedule) 和 [210. Course Schedule II](/interview/coding/210-course-schedule-ii) 的進階問題，其實它更像是 Course Schedule III —— LeetCode 上真正叫 Course Schedule III 的那題反而不像這個系列。

## 思路

「最少」是這題最需要燒腦的點。我寫 LeetCode 的時候，會希望先從之前題目的經驗慢慢展開題目的核心。

先不心急，照搬之前的程式碼，起碼我們知道一件事：**如果有環就直接回傳 -1**。而且找答案的成本頂多和找環一樣，兩倍相同的時間複雜度並不會真的增加量級 —— 所以不如把找環當成回答題目的一部分，找出「最少」是另一部分，寫出來再看能不能合併。

### 最少學期數 = 最長那條依賴鏈的長度

這是整題的核心等式。兩個方向夾一次：

- **至少要這麼多**：如果有一條 `A → B → C → D` 的依賴鏈，那 A、B、C、D 一定得分在四個不同學期（每一門都要等前一門修完）。所以答案不可能小於最長鏈的長度
- **這麼多就夠了**：每個學期都把「所有能修的課」一次修完，那麼一門課會在「它最長的前置鏈長度 + 1」那個學期被修到，不會更晚

所以答案就是最長鏈的長度。這也解釋了兩種極端：

```text
1 → 2 → 3 → 4       一條鏈       → 4 個學期
1 → 2, 1 → 3, 1 → 4  扇狀        → 2 個學期
```

**「最少幾個學期」聽起來像最佳化問題，其實是在問一條路徑有多長。**

想通之後，剩下的招就兩個：BFS 或 DFS。

## 解題方向

### BFS：入度分層（Kahn）

這是最直接對應「一個學期一輪」的寫法 —— **每一輪迴圈就是一個學期**，同一輪裡的課彼此沒有依賴，可以一起修。

分層的手法跟 [102 層序遍歷](/interview/coding/102-binary-tree-level-order-traversal) 一模一樣：**進迴圈前先固定 `len(queue)`**。

```python
class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        graph = {i: [] for i in range(1, n + 1)}
        indegree = {i: 0 for i in range(1, n + 1)}
        for prevCourse, nextCourse in relations:
            graph[prevCourse].append(nextCourse)
            indegree[nextCourse] += 1

        queue = deque([])
        for node in graph:
            if indegree[node] == 0:
                queue.append(node)
        step = 0
        studied = 0
        while queue:
            step += 1
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                studied += 1
                for child in graph[node]:
                    indegree[child] -= 1
                    if indegree[child] == 0:
                        queue.append(child)
        return step if studied == n else -1

```

**環的偵測是免費的**：環上的課永遠沒有人能把它的入度減到 0，所以永遠進不了佇列。`studied != n` 就代表有課卡住了。

注意課程編號是 **1 到 n**，所以是 `range(1, n + 1)` 不是 `range(n)`。

### DFS：記憶化求最長鏈

另一條路是直接算「從每門課出發的最長鏈」，這就是 [329. Longest Increasing Path in a Matrix](/interview/coding/329-longest-increasing-path-in-a-matrix) 的形狀 —— 那題的答案基本上就是這題的最後一段。

**而找環和算長度可以在同一次遞迴裡做完**，用 [207](/interview/coding/207-course-schedule) 的三色標記：

```python
class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        graph = defaultdict(list)
        for prevCourse, nextCourse in relations:
            graph[prevCourse].append(nextCourse)

        state = [0] * (n + 1)      # 0 白（沒走過）/ 1 灰（在這條路上）/ 2 黑（算完了）
        longest = [0] * (n + 1)    # 從這門課出發的最長鏈長度

        def dfs(course):
            if state[course] == 1:
                return -1          # 撞到自己這條路上的課 → 有環
            if state[course] == 2:
                return longest[course]

            state[course] = 1
            best = 1               # 至少有自己這一門
            for nxt in graph[course]:
                res = dfs(nxt)
                if res == -1:
                    return -1      # 環往上傳播
                best = max(best, res + 1)
            state[course] = 2
            longest[course] = best
            return best

        ans = 0
        for course in range(1, n + 1):
            res = dfs(course)
            if res == -1:
                return -1
            ans = max(ans, res)
        return ans
```

`best = 1` 而不是 0 —— 一門課自己就佔一個學期。這跟 329 那篇「要在後面才 `+1`」是同一個坑的兩種寫法：在這裡是從 1 起算，在 329 是最後才加。

`-1` 一路往上傳播，所以不需要先跑一次找環再跑一次算長度，**一次遞迴就結束**。這就是把「找環」和「算最少學期」合併的方式。

### 兩種寫法怎麼選

| | BFS 分層 | DFS 記憶化 |
|---|---|---|
| 直接對應題意 | **是**（一輪 = 一學期） | 不是（要先想通「最長鏈」那層轉換） |
| 環怎麼偵測 | 免費（`studied != n`） | 靠三色標記，`-1` 往上傳 |
| 遞迴深度 | 沒有遞迴 | 最壞 $O(n)$ |

這題我會選 BFS —— 它跟題意的距離最短，`step` 就是學期數，不需要額外的推導。DFS 版的好處是「記憶化」的部分很通用，換成問「最長鏈上有哪些課」之類的變形時比較好改。

## 補充

**這一篇的 DFS 段落原本有三個問題**，都已經修掉：

| 問題 | 原本 | 後果 |
|---|---|---|
| 函式名不符 | 定義 `hasCycle` 但裡面呼叫 `backtrack` | `NameError`，直接跑不起來 |
| 索引錯 | `for i in range(n)` | 課程是 1 到 n，這樣會從不存在的 0 開始、而且**永遠不從課程 n 出發**。像 `n=1, relations=[[1,1]]` 這種只有課程 1 有環的情況會漏判 |
| 空輸入的語意 | `if not relations: return -1` | 沒有先修關係代表所有課可以同一學期修完，答案是 **1** 不是 -1 —— 這一版跟 BFS 版對同一個輸入會給出不同答案 |

前兩個是打錯字，第三個是真的想錯了 —— 值得記住的是：**「沒有限制」通常代表最好的情況，不是無解。**

**拓撲排序家族**：

| 題目 | 問什麼 | 好寫的解法 |
|---|---|---|
| [207. Course Schedule](/interview/coding/207-course-schedule) | 有沒有環 | 都可以 |
| [210. Course Schedule II](/interview/coding/210-course-schedule-ii) | 一組合法順序 | 都可以 |
| 1136 | **最少幾層** | **BFS 分層** |
| [269. Alien Dictionary](/interview/coding/269-alien-dictionary) | 字典序 | 難在建圖，排序用 Kahn |

**分層問題就用 BFS** —— DFS 沿著一條路鑽下去，天生沒有「同一層」的概念，只能靠「最長鏈」繞一圈回來。同樣的道理也出現在 [111. Minimum Depth](/interview/coding/111-minimum-depth-of-binary-tree)（BFS 碰到第一個葉節點就能收工）。

## 複雜度

設 $V = n$ 是課程數、$E$ 是先修關係數。兩種寫法都是：

- 時間 $O(V + E)$ — 每門課處理一次、每條關係走一次
- 空間 $O(V + E)$ — 圖本身；BFS 版另外是佇列 $O(V)$，DFS 版是 `state`、`longest` 加上最壞 $O(V)$ 的遞迴深度

DFS 版在一條長鏈上遞迴深度會是 $V$，而這題的 `n` 上限是 5000 —— Python 預設的 `recursionlimit` 是 1000，所以那種輸入需要調高上限（判題環境通常已經調過）。BFS 版沒有這個顧慮。