1136. Parallel Courses
給 n 門課（編號 1 到 n）和一組先修關係，同一個學期可以修任意多門沒有先修衝突的課。問最少幾個學期修完，修不完回傳 -1。
這個題目是 207. Course Schedule 和 210. Course Schedule II 的進階問題，其實它更像是 Course Schedule III —— LeetCode 上真正叫 Course Schedule III 的那題反而不像這個系列。
思路
「最少」是這題最需要燒腦的點。我寫 LeetCode 的時候，會希望先從之前題目的經驗慢慢展開題目的核心。
先不心急，照搬之前的程式碼，起碼我們知道一件事：如果有環就直接回傳 -1。而且找答案的成本頂多和找環一樣，兩倍相同的時間複雜度並不會真的增加量級 —— 所以不如把找環當成回答題目的一部分，找出「最少」是另一部分，寫出來再看能不能合併。
最少學期數 = 最長那條依賴鏈的長度
這是整題的核心等式。兩個方向夾一次：
- 至少要這麼多：如果有一條
A → B → C → D的依賴鏈，那 A、B、C、D 一定得分在四個不同學期（每一門都要等前一門修完）。所以答案不可能小於最長鏈的長度 - 這麼多就夠了：每個學期都把「所有能修的課」一次修完，那麼一門課會在「它最長的前置鏈長度 + 1」那個學期被修到，不會更晚
所以答案就是最長鏈的長度。這也解釋了兩種極端：
1 → 2 → 3 → 4 一條鏈 → 4 個學期
1 → 2, 1 → 3, 1 → 4 扇狀 → 2 個學期
「最少幾個學期」聽起來像最佳化問題，其實是在問一條路徑有多長。
想通之後，剩下的招就兩個：BFS 或 DFS。
解題方向
BFS：入度分層（Kahn）
這是最直接對應「一個學期一輪」的寫法 —— 每一輪迴圈就是一個學期，同一輪裡的課彼此沒有依賴，可以一起修。
分層的手法跟 102 層序遍歷 一模一樣：進迴圈前先固定 len(queue)。
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 的形狀 —— 那題的答案基本上就是這題的最後一段。
而找環和算長度可以在同一次遞迴裡做完，用 207 的三色標記：
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 往上傳 |
| 遞迴深度 | 沒有遞迴 | 最壞 |
這題我會選 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 | 有沒有環 | 都可以 |
| 210. Course Schedule II | 一組合法順序 | 都可以 |
| 1136 | 最少幾層 | BFS 分層 |
| 269. Alien Dictionary | 字典序 | 難在建圖，排序用 Kahn |
分層問題就用 BFS —— DFS 沿著一條路鑽下去，天生沒有「同一層」的概念，只能靠「最長鏈」繞一圈回來。同樣的道理也出現在 111. Minimum Depth（BFS 碰到第一個葉節點就能收工）。
複雜度
設 是課程數、 是先修關係數。兩種寫法都是：
- 時間 — 每門課處理一次、每條關係走一次
- 空間 — 圖本身；BFS 版另外是佇列 ，DFS 版是
state、longest加上最壞 的遞迴深度
DFS 版在一條長鏈上遞迴深度會是 ，而這題的 n 上限是 5000 —— Python 預設的 recursionlimit 是 1000，所以那種輸入需要調高上限（判題環境通常已經調過）。BFS 版沒有這個顧慮。