題目與適用情境
有 numcourses 門課程，編號為 0 到 numcourses - 1。每筆先修關係 [course, prerequisite] 表示必須先修完 prerequisite，才能修 course。請回傳任一能完成 全部課程的順序；若沒有可行順序，回傳空串列。
本題約定 0 <= num_courses <= 2000，課程編號有效，每對關係互不相同，而且輸入中沒有自己 相依自己的邊。num_courses == 0 時回傳空串列。對於 num_courses = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]， [0, 1, 2, 3] 與 [0, 2, 1, 3] 都正確；對於 [[1, 0], [0, 1]]，兩門課彼此相依，只能回傳空串列。
這是一道適合一般軟體工程職缺的程式題，核心是把自然語言中的相依關係轉成有向圖，再判斷圖是否 為有向無環圖。基本題只要求任一合法順序，不要求字典序最小，也不計算每門課的耗時或同時修課上限。
面試官評估重點
第一個訊號是邊的方向。[course, prerequisite] 應建立 prerequisite -> course，因為完成先修課後才能釋放後續課程。反向建圖仍可能跑出一個排列， 但排列表達的是相反限制，無法回答題目。
第二個訊號是能否從「目前可以選的課程」推導入度。某門課的入度代表尚未滿足的直接先修課數量。 入度為零才能進入候選佇列；完成一門課後，只減少它直接後繼的入度。好的回答會說清楚這個狀態含義， 而非只背誦「用 BFS」。
第三個訊號是環偵測。不能因為佇列變空就直接回傳已取得的部分順序。只有結果長度等於課程總數時， 所有節點才都被處理；長度不足表示剩餘子圖沒有零入度節點，其中必定有有向環。
面試官也會檢查複雜度、邊界與契約意識。鄰接串列實作需要 O(V + E) 時間與空間；使用 deque.popleft() 能讓佇列前端移除維持常數時間。多種合法順序、互不連通的課程、空輸入和長相依鏈 都應出現在測試中。
回答前需要釐清的問題
- 回傳任意順序或字典序最小順序？ 任意順序使用一般佇列即可；字典序最小要用最小堆積，
時間會變成 O(E + V log V)。
- 先修關係可能重複嗎？ 本題保證互不相同。若不保證，可以保留重複邊並同步累加入度，
或在建圖時去重；不能只去重其中一邊，否則入度永遠無法降到零。
- 輸入可能有無效編號或自環嗎？ 本題假設呼叫端已驗證。若需要防禦式 API，應先定義要拋錯
或回傳空串列，避免把「輸入無效」與「存在相依環」混成同一結果。
- 只需要一個順序，還是所有合法順序？ 一個順序是線性圖走訪；列舉所有順序要在每一步嘗試
所有零入度課程，最差輸出量接近階乘級。
- 課程能否平行修習？ 基本題回傳線性排列。若要在每學期容量無限時求最少學期數，應按佇列
層級批次處理；若課程有不同耗時，則要在 DAG 上計算最長相依路徑。
- 規模能否放入記憶體？ 在
V <= 2000下，鄰接串列足夠直接。邊無法全放入記憶體時，
需要外部儲存或分割處理，已超出這道程式題的邊界。
30 秒回答架構
「我會把每門課當成節點，把 [course, prerequisite] 建成 prerequisite -> course，並統計每門課的入度。先將所有零入度課程放進佇列；每次取出一門課加入 結果，走訪它的後繼並把入度減一，新變成零的課程再入列。佇列中的課程正好是目前所有先修要求都已 滿足的未處理課程，所以依這個順序選擇始終安全。結束時若結果長度等於課程數就回傳結果；否則剩餘 節點包含環，回傳空串列。鄰接串列方案的時間與額外空間都是 O(V + E)。」
分步深入解答
最直接的想法是反覆掃描所有未選課程，找出先修課都已出現在結果中的課程。即使以集合記錄已完成 課程，每輪仍可能檢查全部邊；在長鏈輸入中需要做 V 輪，時間可能到 O(VE)。瓶頸是反覆重新 計算同一相依關係是否已滿足。
Kahn 演算法把這項資訊增量維護成入度。令 graph[u] 儲存完成課程 u 後可能被釋放的課程， indegree[v] 儲存課程 v 尚未滿足的直接先修課數。建圖時遇到 [course, prerequisite]，把 course 加入 graph[prerequisite]，並增加 indegree[course]。
演算法維護兩個不變量：
indegree[v]等於從尚未處理節點指向v的邊數。- 佇列包含且只包含所有尚未處理、剩餘入度為零的課程。
初始統計顯然滿足第一個不變量，把所有零入度節點入列後也滿足第二個。取出課程 u 時，它沒有 來自未處理課程的先修限制，因此將它加入結果是安全的。移除 u 的影響等同於走訪 graph[u] 並減少每個後繼的入度；某個後繼第一次變成零時入列，兩項不變量繼續成立。
from collections import deque
def find_course_order(
num_courses: int,
prerequisites: list[list[int]],
) -> list[int]:
graph = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, prerequisite in prerequisites:
graph[prerequisite].append(course)
indegree[course] += 1
ready = deque(
course for course, degree in enumerate(indegree) if degree == 0
)
order: list[int] = []
while ready:
course = ready.popleft()
order.append(course)
for dependent in graph[course]:
indegree[dependent] -= 1
if indegree[dependent] == 0:
ready.append(dependent)
return order if len(order) == num_courses else []若所有課程都被取出，不變量保證每門課加入結果時，其先修課都已在前面，因此結果合法。若結果短於 V，剩餘有限子圖中每個節點的剩餘入度都大於零。從任一節點持續沿一條入邊往前追溯，有限節點 必然使某個節點重複，重複區段形成有向環；所以不可能完成全部課程。這也說明長度檢查同時完成環偵測。
每個節點入列、出列至多一次，每條邊在建圖與釋放後繼時各處理一次，時間為 O(V + E)。 鄰接串列、入度陣列、佇列與結果合計使用 O(V + E) 空間。這裡使用 deque，因為從 Python 串列前端 pop(0) 會搬移其餘元素，可能讓佇列操作退化成線性時間。
對抗性驗證應檢查結果性質，而非只比對某個固定答案：結果必須包含恰好 V 個不重複編號，而且 每筆 [course, prerequisite] 中 prerequisite 的位置都小於 course。測試至少包含空輸入、 單節點、全部獨立、單條長鏈、菱形相依、多個互不連通元件和有向環。菱形圖尤其能防止把「任一合法 順序」誤寫成「必須符合某個固定陣列」。
DFS 也能完成拓撲排序：使用白、灰、黑三色標記，遇到指向灰色節點的邊就發現環，節點退出遞迴時 加入結果，最後反轉後序。它適合同時回傳一條具體環路徑，但 Python 中的長鏈可能觸發遞迴深度限制。 Kahn 演算法直接呈現「目前可修課程集合」，較容易擴充成平行學期，因此是本題更直接的首選。若規模 很小且只問可行性，反覆掃描的簡單方案可能更短；面試時應明確說出它的最差複雜度。
高品質示範回答
「我先確認只需回傳任一合法順序，並假設課程編號和相依邊都有效且不重複。每筆關係 [course, prerequisite] 表示一條由先修課指向課程的邊。如此一來，課程的入度就是還有多少直接 先修課尚未完成。
我會建立鄰接串列與入度陣列，把所有入度為零的課程加入 deque。迴圈中從前端取一門課放入答案， 再走訪它的後繼，把這些後繼的入度減一；只有入度剛變成零時才入列。關鍵不變量是：佇列中正好是 目前沒有未完成先修要求的課程，所以每次選擇都不會違反相依關係。
迴圈結束後不能無條件回傳。答案長度等於課程總數時，所有相依關係都滿足；長度不足時，剩餘節點 都還有入邊，在有限圖中沿入邊追溯必定會回到走過的節點，因此存在環，我會回傳空串列。
鄰接串列使每個節點與每條邊只被處理常數次，時間為 O(V + E)，空間也是 O(V + E)。我會用 空圖、單節點、長鏈、菱形多解、斷開的元件與二節點環測試。驗證多解時，我會檢查每條先修邊的相對 位置，不會把結果限定成某一個固定排列。」
常見錯誤
- 把邊建成
course -> prerequisite→ 輸出可能把課程排在先修課之前 → **依「完成哪個節點會
釋放哪些節點」建立 prerequisite -> course。**
- 只從課程 0 開始走訪 → 獨立元件會被漏掉 → 初始化時掃描全部節點，將所有零入度節點入列。
- 佇列為空就回傳部分結果 → 有環輸入被誤判為成功 → **只有
len(order) == num_courses才
回傳順序。**
- 同一節點多次入列 → 結果出現重複課程 → 只在入度由 1 降到 0 的那次入列。
- 用
list.pop(0)實作佇列 → 長輸入中反覆搬移元素 → 使用deque.popleft()。 - 拿輸出與固定拓撲序比較 → 另一個合法順序被判錯 → 檢查唯一性、長度和每條邊的相對位置。
- 圖去重但入度不去重，或反過來 → 重複邊契約下計數不一致 → **要完整保留重複邊，或在建圖時
統一對邊去重。**
- 宣稱額外空間為
O(V)→ 鄰接串列還儲存全部邊 → 依稀疏圖實作回報O(V + E)。 - 使用 DFS 卻沒有走訪中狀態 → 環上的節點會被重複遞迴或錯誤完成 → **至少使用三色狀態區分
走訪中與已完成。**
追問與應對
追問 1：如何回傳字典序最小的合法順序？
將一般佇列換成最小堆積。每次從所有目前零入度課程中取編號最小者，可透過貪心交換論證得到 字典序最小結果。邊處理仍為 O(E)，節點進出堆積使時間變成 O(E + V log V)；若只需任意 順序，一般佇列更簡單也更快。
追問 2：如果每學期可以同時修任意多門課，最少需要幾個學期？
依佇列目前長度分層處理：同一層的課程在這學期同時完成，它們釋放的零入度後繼進入下一層。 每完成一層，學期數加一。這個結論依賴所有課程耗時相同且同時修課容量無限；若每學期最多修 k 門，簡單分層不再保證全域最佳。
追問 3：每門課耗時不同，如何得到最早畢業時間？
先取得拓撲序，再依該順序做 DAG 動態規劃。課程最早開始時間是所有先修課最早完成時間的最大值， 加上自身耗時得到最早完成時間。答案是所有課程最早完成時間的最大值。不能直接用 Kahn 演算法的 層數，因為一門耗時十週的課與一門耗時一週的課並不等價。
追問 4：如何回傳造成失敗的一條具體相依環？
Kahn 演算法能判斷剩餘子圖有環，但不直接保留環路徑。可以在剩餘節點上執行三色 DFS，並記錄父 節點；遇到指向灰色節點的邊時，沿父指標回溯即可建立一條環。若診斷資訊是核心需求，也可從一開始 就使用帶父指標的 DFS 拓撲排序。
追問 5：持續新增相依邊時，如何維護順序？
低頻更新時，加入新邊後重新執行 O(V + E) 拓撲排序最可靠，也最容易驗證。更新頻繁且圖很大時， 可維護節點目前位置：若新邊已符合當前順序，無須調整；否則只在受影響區間檢查可達性並重排。動態 拓撲排序實作複雜，面試中應先以更新頻率與圖規模證明它值得引入。
追問 6：如何列舉所有合法修課順序？
使用回溯：每一步列舉所有目前零入度節點，暫時選擇一個、更新後繼、遞迴，再還原入度。它會避開 非法排列，但合法順序數量本身可能接近 V!，所以時間至少與輸出規模成正比。要先確認上限很小， 並討論是否只需計數、抽樣或前 k 個結果。