210. Course Schedule II

──────────────────────────────────────────────────────────────────────

跟 207 一樣的輸入，但不只要判斷能不能修完，還要回傳一組合法的修課順序；有環就回傳空陣列。

思路

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

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

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

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

graph[course].append(prerequisite)

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

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

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

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

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

解題方向

後序 DFS

主體跟 207 的方法三完全一樣，只是多了一行 order.append：

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

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 的「兩個布林，其實只有三種狀態」，這裡不重複。）

BFS

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

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 的工作：排不完就代表有環（為什麼排不完就一定有環）。

補充

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

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

家族：

題目	變化
207. Course Schedule	有沒有環
210	輸出一組合法順序
269. Alien Dictionary	難在建圖 —— 從相鄰兩個單字的第一個相異字元推出邊
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)$ ，不計入額外空間。