207. Course Schedule

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

207. Course Schedule

給 numCourses 門課和一組 [課程, 先修課] 的關係，問所有課能不能修完。

這一個題目的設計滿巧妙的，我個人覺得它綜合了樹的遍歷（遞迴）、回溯法、動態規劃以及資料與圖形轉換的設計，外加上題目可以套用在各種現實生活問題中。所以整體而言 LeetCode 給出了中等難度，但是細節很多很需要小心的想通。

而且我不得不承認，每次我在複習這個題目的時候，都還是要花點時間去推敲整個題目的細節。

思路

其實這個題目滿貼近大學時的生活的，那就是很多科目都有擋修，那系上設計這個課程的時候，不能怎麼樣設計？舉例來說：系上的課程不能說這樣，要修過計算機概論才能修演算法，要修過演算法要才能資料結構，然後要修過資料結構才能修計算機概論，這就充滿了邏輯的矛盾，這個題目就是要看有沒有這種矛盾。

目標於是很明確：這個課程的前後關係，會不會造成環。 有環代表「A 要先修 B、B 要先修 C、C 又要先修 A」，永遠開不了頭。

「走過」和「有環」不是同一件事

這是這題最容易錯的地方。走訪時遇到一個看過的節點，不代表有環：

      0
     / \
    1   2
     \ /
      3

從 0 出發，走 0→1→3 之後回頭走 0→2→3，會第二次遇到 3 —— 但這張圖沒有環。

只有遇到「還在目前這條路徑上」的節點，才是環。

先把資料轉成圖

課程和先修課的關係本身就是一張有向圖：把每門課當成一個節點，「A 的先修課是 B」就是一條 A 指向 B 的邊。

（原本我把它想成「一棵或很多棵樹」，那個直覺方向是對的，但嚴格說它是圖不是樹 —— 一門課可以同時是很多門課的先修課，也就是一個節點可以有多個「父親」。真正的差別在於圖可能有環，樹不會，而這題要找的就是環。）

題目給的是一個沒有特定排列順序的數列，如同其他很多圖的題目，第一步先建立整個圖。但是在這裡，我們其實就會有第一個要討論的地方，那就是我們透過 Hash Table 這個資料結構時，方向有沒有關係？

• 課程 → 所有先修課
• 先修課 → 所有被擋修的課程

這邊我想要先把 210. Course Schedule II 稍微拿出來討論一下，這兩個題目的差別就在於是否要給出修課的路徑。

其實如果我們把上面的例子稍微看一下，就會發現其實兩個方向都是可以的，我們從哪個方向去檢查，只要沒有環就可以了（下面兩個迴圈是二選一，不是兩個都建）

graph = defaultdict(list)
# 課程 → 所有先修課
for course, prerequisite in prerequisites:
    graph[course].append(prerequisite)
# 先修課 → 所有被擋修的課程
for course, prerequisite in prerequisites:
    graph[prerequisite].append(course)

（這個結論只在「只要判斷有沒有環」的前提下成立。等一下寫到 BFS 的時候會發現，換一個問法之後方向就被鎖死了。）

那到底要選什麼演算法？

這裡其實大概就可以想到要使用 BFS / DFS 來解題了，因為我們就要開始遍歷這個圖，這裡也是比較困難的細節要處理。

我們可以用一個圖去思考，在做單純的 BFS / DFS 的時候，我們通常會去記錄已經造訪過的節點，在下方的圖片，我如果從 0 開始出發走過一個路徑 0 → 1 → 2 → 4，這時候 1 已經造訪過了，但是我們不能把它標記成不能再次造訪，因為如果這樣的話，我們就沒辦法檢查 0 → 1 → 3 → 4 這個路徑了，所以這也是如果我們要使用 BFS / DFS 時要注意的地方。

寫到這邊，其實我就會開始選擇使用 DFS 因為展開後其實就是 Backtracking 的做法，我會在後面繼續討論 BFS 的想法是什麼。

    0 
     \ 
      1
     / \
    2   3
     \ /
      4

解題方向

方法一：回溯法（超時）

透過最後的 for 迴圈，我們要檢查每一門課，看它底下是否有環。

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

        for course, prerequisite in prerequisites:
            graph[course].append(prerequisite)
        
        def hasCycle(course, on_path):
            if course in on_path:
                return True
            on_path.add(course)
            for child in graph[course]:
                if hasCycle(child, on_path):
                    return True
            on_path.remove(course)
            return False

        for course in range(numCourses):
            if hasCycle(course, set()):
                return False
        
        return True

這個集合原本我命名成 visited，但那個名字會誤導 —— 它裝的不是「造訪過的節點」，而是「目前這條路徑上的節點」，所以改叫 on_path。

那個 if course in on_path: return True 為什麼成立

因為結尾有 on_path.remove(course)。進入時加、離開時移除，所以在任何時刻，on_path 裝的剛好就是「從起點走到我現在位置」的那條路徑 —— 它是遞迴堆疊的鏡子。

既然 on_path = 目前這條路，那「走到一個已經在裡面的節點」就是說：有一條路從它出發，繞了一圈又回到它自己。那就是環。

有環的時候（0 需要 1、1 需要 2、2 需要 0）：

進入 0，on_path = []
  進入 1，on_path = [0]
    進入 2，on_path = [0, 1]
      進入 0，on_path = [0, 1, 2]
      → 0 已經在裡面 → True

沒有環的時候（上面那張菱形圖），remove 的作用就看出來了：

進入 0，on_path = []
  進入 1，on_path = [0]
    進入 3，on_path = [0, 1]
    離開 3，移除後 on_path = [0, 1]
  離開 1，移除後 on_path = [0]
  進入 2，on_path = [0]          ← 1 和 3 都已經被移掉
    進入 3，on_path = [0, 2]      ← 3 不在裡面，正常展開

如果把 remove 拿掉，第二次走到 3 就會被誤判成環：

  進入 2，on_path = [0, 1, 3]    ← 1 和 3 還留著
    進入 3，on_path = [0, 1, 2, 3]
    → 3 已經在裡面 → True         ← 誤判

所以 if ... return True 和 remove 是一組的，缺一個就錯。remove 是讓那個 return True 成立的前提。

為什麼會超時

題目的範例都沒有問題，但是這樣的方法會超時。因為如果有 $n$ 門課程，相當於我們要遍歷這麼多棵樹；如果說第 $i$ 門課有先修課 $k$，那這樣的方法就會在探索時，再次檢查第 $k$ 門課是不是有環的存在。有點像是動態規劃的子問題 —— 同一個子問題被重算了很多次。

方法二：回溯法＋記憶

方法一會超時的原因是，我們不斷地去檢查已經檢查過的課程。更好的方法是：當一門課確定底下沒有環之後，就把這個結論記起來，下次直接用。

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

        for course, prerequisite in prerequisites:
            graph[course].append(prerequisite)
        
        memo = [False] * numCourses # 這門課底下已經確認沒有環
        
        def hasCycle(course, on_path):
            if course in on_path:
                return True
            if memo[course]:
                return False
            on_path.add(course)
            for child in graph[course]:
                if hasCycle(child, on_path):
                    return True
            on_path.remove(course)
            memo[course] = True # 底下確定沒有環
            return False

        for course in range(numCourses):
            if hasCycle(course, set()):
                return False
        
        return True

memo 在這裡記錄的是「這門課底下已經確認沒有環」，所以當我再次看到 k 課程時，我不用再去遍歷一次所有的路徑，上面是做了類似動態規劃的記憶法，去記憶已經驗證過的的課程，時間複雜度也變成線性。

我的筆記算是紀錄從面試作答，到怎麼樣在面試中慢慢走到現在這一步，取決於面試所剩下的時間，面試官可能會覺得這樣就好了。但是這裡有一個可以優化的地方，那就是我們能不能再去簡化記憶的這個過程？

這會是一個更難的 follow up 問題，所以我們要分析這件事情，那就是當我們進入到一個節點（課程）的時候，需要注意什麼？這裡會需要從我們當前的最後一個答案開始分析回去。

兩個布林，其實只有三種狀態

我一開始想不到「用一個結構管三種狀態」，是因為我直接去想答案長什麼樣子。應該反過來：先老實地把方法二進入一個節點時問過的問題列出來，再去看這些問題彼此的關係。

def hasCycle(course, on_path):
    if course in on_path:   # 問題一
        return True
    if memo[course]:        # 問題二
        return False

兩個布林問題，攤開來是四種組合：

course in on_path	memo[course]	代表什麼
True	False	在目前這條路上 → 有環
False	True	已經確認底下沒有環
False	False	沒碰過，要展開
True	True	不會發生

第四種永遠不會發生，而且原因就寫在程式碼的順序裡：memo[course] = True 這一行在 on_path.remove(course) 的後面。一個節點是先離開路徑，才被標記成完成的，所以它不可能同時「還在路上」又「已經完成」。

四種組合只用到三種，那就不是兩個獨立的旗標，而是一個有三個值的狀態被我拆成了兩個變數。 這個判斷方式可以直接帶去別題：只要幾個布林值之間互相排斥、組合數用不滿，通常就是同一個狀態被拆開了。

而且這三種不是隨便三種，它剛好就是一個節點在 DFS 裡的生命週期：

沒碰過  →  正在處理（在目前這條路徑上）  →  處理完（底下確定沒有環）

生命週期是單向的，不會倒退。這一點回頭解釋了 remove：在方法二裡它看起來像是「把節點放回沒碰過」，但它後面緊接著 memo[course] = True，兩行加起來才是一個完整的動作 —— 離開路徑，然後往前走到「處理完」。我需要寫成兩行，只是因為我用兩個結構去存一件事。

接下來就是把這三個狀態寫成一個結構，看看程式碼會少掉哪些東西。

方法三：一個 state 管三個狀態

不要叫 visited，那個名字在這篇已經害我一次了。叫 state，因為它回答的是「這個節點現在在哪個階段」，不是「有沒有看過」。

寫法一：用 dict

key 在不在代表「有沒有碰過」，value 的布林代表碰過之後的那兩個狀態。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

        graph = defaultdict(list)

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

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

        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
            return False

        for course in range(numCourses):
            if hasCycle(course):
                return False

        return True

這裡要用 is 而不是直接判斷真假值，因為沒碰過時 get 回傳的是 None，而 None 和 False 都是 falsy，直接寫 if not state.get(course) 會把「沒碰過」也當成「正在處理」。

收尾是 state[course] = True，不是 del state[course]。刪掉 key 等於把它退回「沒碰過」，記憶就沒了，會退回方法一的超時。刪掉還是改值，就是方法一和方法三的差別。

寫法二：用陣列

這題的節點剛好是 0 到 numCourses - 1 的密集整數，所以直接開一個等長的陣列，三個狀態就用三個數字。dict 的價值在節點是字串或稀疏 id 的時候。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

        graph = defaultdict(list)

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

        UNVISITED, VISITING, DONE = 0, 1, 2
        state = [UNVISITED] * numCourses

        def hasCycle(course):
            if state[course] == VISITING:
                return True
            if state[course] == DONE:
                return False
            state[course] = VISITING
            for child in graph[course]:
                if hasCycle(child):
                    return True
            state[course] = DONE
            return False

        for course in range(numCourses):
            if hasCycle(course):
                return False

        return True

一份 state 共用會不會互相汙染？

方法二的 on_path 是每條路徑各自一份，外圈每跑一次就給一個新的 set()；方法三的 state 是整份共用，跨外圈的每一輪都留著。直覺上這應該要出事才對。

但它不會，因為 VISITING 只存在於遞迴展開的期間。外圈跑到下一輪時，上一輪的遞迴已經全部結束了，所以那時候 state 裡只剩 UNVISITED 和 DONE，不可能有殘留的 VISITING 去誤導下一輪。

留下來的 DONE 也正是我們要的 —— 那就是方法二的 memo。

方法四：BFS

前面提到的 BFS 在這裡，其實用想像的方式去看 BFS 好像還是可以解得出題目，但是實作上卻很困難，尤其是如果把 DFS 的找環的方式來 BFS 做，可能會讓面試時失敗，DFS 問的是：這門課往下追它的先修課，會不會繞回它自己？

BFS 我必須承認我想不出來，是後來看解答才想到的。

• BFS 問的是：現在有哪些課是馬上就能修的？修完它之後，又解鎖了哪些課？

順著第二個問法往下想，需要的東西就一個一個掉出來了：

1. 「馬上就能修」代表它沒有任何還沒修完的先修課。所以我要能查一門課還欠幾門先修課，那就開一個 indegree 陣列來記。
2. 「修完 A 之後解鎖了誰」代表我要能從 A 查到被 A 擋住的課。這一步就把圖的方向鎖死成 先修課 → 課程。
3. 解鎖的動作就是把那些課的 indegree 減一，減到 0 就代表它可以修了，丟進佇列。
4. 佇列空掉的時候推不動了，這時候看修完的課數有沒有等於 numCourses。207 要的就只是這個布林。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

        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)
        finished = 0

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

        return finished == numCourses

這一版完全沒有遞迴，也沒有「還在不在路徑上」這個概念 —— 因為它根本不走路徑。

為什麼「排不完的那些課一定在環裡」

這是這個解法唯一需要證明的地方，也是面試時要能講出口的一句。

假設某門課 X 到最後都沒有被彈出佇列，那代表 X 的 indegree 從頭到尾沒有歸零，也就是至少有一門先修課 Y 也沒有被修到。同樣的道理套在 Y 身上，Y 也一定有一門沒被修到的先修課 Z⋯⋯

這條「每一門都還有前一門」的鏈可以無限往前追，但課程總數是有限的，所以一定會追到某一門重複出現。重複出現就是繞回來了，那就是環。

反過來也成立：如果沒有環，每一輪一定至少有一門課的入度是 0（否則就會出現上面那條無限鏈），所以佇列不會提前空掉，最後 finished 一定等於 numCourses。

回頭看「方向到底有沒有關係」

前面建圖的時候我說兩個方向都可以，那句話只在「判斷有沒有環」的前提下成立 —— DFS 從哪一頭走都會踩到同一個環。

但問法一換成「解鎖」，方向就沒得選了：

我要問的事	圖的方向
有沒有環（DFS）	兩個方向都行
現在能修哪些課、修完解鎖誰（Kahn）	只能 先修課 → 課程
輸出一組修課順序（210）	方向決定要不要反轉結果

所以這題的四個解法裡，前三個用 課程 → 先修課，只有 Kahn 這版反過來。不是我隨便換的，是問法逼出來的。

複雜度

方法一：回溯法

• 時間 $O(2^n)$ — 每門課都要重新列舉它底下的所有路徑，而路徑數最壞會隨課程數指數成長
• 空間 $O(n+m)$ — 圖佔 $O(m)$，遞迴堆疊和 on_path 最深 $O(n)$

方法二：回溯法＋記憶

• 時間 $O(n+m)$ — 每門課只會真的被展開一次，之後都被 memo 擋掉；每條先修關係只走一次
• 空間 $O(n+m)$ — 圖 $O(m)$，memo、on_path 和遞迴堆疊各 $O(n)$

方法三：三個狀態

• 時間 $O(n+m)$ — 跟方法二一樣，每個節點的狀態只會單向從 UNVISITED 走到 DONE
• 空間 $O(n+m)$ — 一樣，但少一個結構：on_path 和 memo 併成一個 state

方法四：入度 ＋ BFS

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

其中 $n$ 是課程數，$m$ 是先修關係的數量。