HardRating 2084
2050. Parallel Courses III
arraydynamic-programminggraphtopological-sort
解題說明
Parallel Courses III
題目描述： 有 n 門課程和它們之間的先修關係。每門課有完成時間 time[i]。可以同時修多門課（只要先修條件滿足）。求完成所有課程需要的最短時間。
解題思路： 這是一個 DAG 上的最長路徑問題。使用拓撲排序 + 動態規劃。
- 建立鄰接表和入度陣列。
- dp[i] 表示完成課程 i（含自身）所需的最早完成時間。
- 初始化：所有入度為 0 的課程 dp[i] = time[i]（無先修條件，直接可以開始修）。
- 按拓撲序處理：對每個課程 u，更新其所有後繼 v：dp[v] = max(dp[v], dp[u] + time[v])。
- 答案為所有 dp[i] 的最大值。
這等價於求 DAG 上的關鍵路徑（Critical Path），即最長路徑。
C++ 解法
複雜度分析
時間複雜度：O(n + m) — 拓撲排序遍歷每個節點一次、每條邊一次，其中 m 為先修關係數量。
空間複雜度：O(n + m) — 鄰接表 O(m)，入度陣列和 dp 陣列 O(n)。
虛擬碼
1. Build adjacency list and in-degree array from relations.
2. Initialize dp[i] = 0 for all courses.
3. For each course i with in-degree 0: dp[i] = time[i], enqueue i.
4. While queue is not empty:
a. Dequeue course u.
b. For each successor v of u:
- dp[v] = max(dp[v], dp[u] + time[v]).
- Decrement in-degree of v. If 0, enqueue v.
5. Return max(dp[1..n]).其他解法
-
DFS + 記憶化：從每個節點做 DFS，dp[u] = time[u] + max(dp[v] for all predecessors v)。使用記憶化避免重複計算。時間複雜度相同 O(n + m)，但遞迴深度可能造成堆疊溢位。
-
反向拓撲排序：反轉所有邊的方向，從出度為 0 的節點開始做拓撲排序。dp[u] 表示從 u 出發到結束的最長路徑。最後取 dp 的最大值。本質相同，只是遍歷方向不同。
延伸思考
- 若同一時間最多只能修 K 門課，如何修改演算法？這會將問題變成什麼類型？
- 若課程之間的依賴關係可能形成環（有迴圈依賴），應如何偵測並處理？
- 如何找出「關鍵路徑」上的具體課程，即那些延遲會直接導致總完成時間增加的課程？