📘 題目敘述
總共有 numCourses 門課要修，課程編號從 0 到
numCourses - 1。
給你一個陣列 prerequisites，其中
prerequisites[i] = [ai, bi] 表示：如果你想修課程
ai，你必須先修完課程 bi。
例如，配對 [0, 1] 表示：要修課程 0，你必須先修課程
1。
請回傳你是否能修完所有課程。 如果可以，回傳 true；否則回傳
false。
條件限制
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites中所有配對都互不相同
🧠 解題思路
這題的重點是判斷：課程之間的先修關係圖裡，有沒有環。
如果有環，就代表會出現這種情況：
- 修 A 之前要先修 B
- 修 B 之前要先修 C
- 修 C 之前又要先修 A
那這樣就永遠沒辦法開始，所以答案是 false。
如果沒有環，代表這些課可以照某種順序一路修完，所以答案是
true。
我這份寫法是用 DFS 來檢查圖中有沒有 cycle。
先把課程關係建成 adjacency list：
course[b]裡面放的是：修完b之後，可以接到哪些課- 也就是程式裡這個意思：
course[b].push_back(a);接著我用一個 check 陣列記錄每個點目前的狀態：
0：還沒檢查過1：這個點目前正在 DFS 路徑上2：這個點已經確認沒問題，可以完成
這樣做的關鍵是：
- 如果 DFS 走到某個點時，發現它已經是
1 - 代表我又走回目前遞迴路徑上的點了
- 這就表示圖中有環，直接回傳
false
如果某個點已經是 2，代表它之前已經檢查過，而且從它出發不會遇到環，那這次就不用再重跑，直接回傳
true。
所以這題核心就是：
用 DFS 檢查每個課程出發的路徑上有沒有回到「正在遞迴中的點」，如果有就是有環，不能完成所有課程。
所有變數
-
course：鄰接串列，course[x]表示從課程x可以連到哪些後續課程 check：記錄每個課程的 DFS 狀態0：未檢查1：正在遞迴中2：已確認可完成-
row：在讀prerequisites時，代表其中一組[a, b]
🪜 主要流程步驟
1. 先建立課程關係圖
在 canFinish 裡，先把圖的空間開好：
course.resize(numCourses);
check.assign(numCourses, 0);這裡：
course.resize(numCourses)：讓每門課都有自己的鄰接串列-
check.assign(numCourses, 0)：一開始所有課都還沒檢查，所以全部設成0
接著讀 prerequisites：
for (auto& row : prerequisites) {
int a = row[0];
int b = row[1];
course[b].push_back(a); // b可以到a
}
如果 [a, b] 表示修 a 前要先修
b，那圖上就建一條：
b -> a
意思是：修完 b 之後，才有可能往 a 走。
2. 對每一門課都嘗試做 DFS 檢查
for (int i = 0; i < numCourses; i++) {
if (!dfs(i)) {
return false;
}
}這一步是因為圖不一定連通。
也就是說：
- 有些課程可能在同一個連通塊
- 有些課程可能完全獨立
- 有些課程可能在另一群先修關係裡
所以不能只從某一個點開始 DFS，而是要把每門課都檢查一次。
只要其中有任何一門課在 DFS 過程中發現環，就直接回傳
false。
3. dfs(n) 一進來先看這個點現在是什麼狀態
if (check[n] == 1) {
return false;
}
if (check[n] == 2) {
return true;
}這兩個判斷是整份程式的核心。
第一個：
- 如果
check[n] == 1 - 代表這個點現在正在目前的遞迴路徑上
此時如果又走回它，就表示出現 cycle，所以直接回傳
false。
第二個：
- 如果
check[n] == 2 - 代表這個點之前已經完整檢查過，確定從它出發不會形成環
所以這次不用重算，直接回傳 true。
4. 把目前這個點標記成「正在檢查」
check[n] = 1;這一步的意思是：
- 我現在開始 DFS 這個課程
n - 所以先把它標記成「正在遞迴中」
這樣如果之後沿著它的後續課程一路走，又繞回來看到它，就能判斷出有環。
5. 遞迴檢查所有後續課程
for (int j : course[n]) {
if (!dfs(j)) {
return false;
}
}這裡會把 n 的所有鄰接點都往下檢查。
意思是：
- 如果修完
n之後，可能接到很多課j - 那每一條路都要確認不會形成環
只要其中任何一個 dfs(j) 回傳 false，就代表某條路上有
cycle，那整體就不可能完成所有課程，所以直接回傳
false。
6. 如果所有後續都沒問題，就把它標成「可完成」
check[n] = 2;
return true;如果程式走到這裡，代表：
n的所有後續課程都檢查完了- 沒有任何一條路形成環
所以 n 這個點可以安全完成，之後如果別的 DFS 又走到它，就不必重新檢查了，直接知道它是合法的。
這也是 check == 2 的用途：做記憶化，避免重複 DFS。
7. 為什麼這樣就能判斷能不能修完所有課
這題本質上就是在問：
- 先修課程關係圖是不是 DAG（Directed Acyclic Graph）
如果是 DAG：
- 一定存在某種修課順序
- 所以可以完成所有課程
如果不是 DAG，也就是有環：
- 某些課彼此互相依賴
- 永遠無法開始
- 所以不能完成所有課程
而這份程式就是用 DFS 遞迴時的三種狀態：
0未檢查1正在檢查2已確認安全
來抓出有沒有環。
⏱️ 複雜度
-
時間複雜度：
O(numCourses + prerequisites.length)每個課程與每條先修邊最多被 DFS 檢查一次。 -
空間複雜度：
O(numCourses + prerequisites.length)需要鄰接串列儲存圖，另外check與遞迴堆疊最多也會用到O(numCourses)。
💻 程式碼實作
class Solution {
public:
vector<vector<int>> course;
vector<int> check; // 0是無，1是正在，2是可
bool dfs(int n) {
if (check[n] == 1) {
return false;
}
if (check[n] == 2) {
return true;
}
check[n] = 1;
for (int j : course[n]) {
if (!dfs(j)) {
return false;
}
}
check[n] = 2;
return true;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
course.resize(numCourses);
check.assign(numCourses, 0);
for (auto& row : prerequisites) {
int a = row[0];
int b = row[1];
course[b].push_back(a); // b可以到a
}
for (int i = 0; i < numCourses; i++) {
if (!dfs(i)) {
return false;
}
}
return true;
}
};