題目描述:有 n 門課程,部分課程有先修要求 [a, b] 表示學 a 前必須先學 b,判斷是否能完成所有課程。
解題思路:本題等價於判斷有向圖中是否存在環。建立鄰接表,用 DFS 搭配三色標記法(未訪問=0、訪問中=1、已完成=2)。若 DFS 過程中碰到「訪問中」的節點,說明存在環,回傳 false。也可用 Kahn's 演算法(拓撲排序 + 入度計算)。
時間複雜度:O(V + E) — 每個節點和邊各訪問一次。
空間複雜度:O(V + E) — 鄰接表與狀態陣列。
1. Build adjacency list from prerequisites 2. Initialize state[0..n-1] = 0 (unvisited) 3. For each node i: a. Run DFS: if state[i]==1 → cycle; if state[i]==2 → skip b. Mark state[i]=1 (visiting), recurse on neighbors, mark state[i]=2 4. Return true if no cycle found
DFS 不建鄰接表 O(N²) 時間,O(N) 空間:直接掃描邊列表檢查依賴 — 時間複雜度更差。
使用 Kahn 演算法 (BFS 拓撲排序) O(N+E) 時間,O(N) 空間:計算入度,逐一移除入度為 0 的節點 — 邏輯清晰,檢測環時略不同。