leetcode 210. Course Schedule II [Medium]

題目敘述

給定一個 prerequisites 陣列，每個元素 prerequisites[i] = [a, b] 代表：想選課程 a，必須先修過課程 b。題目要求回傳可能的修課順序；若無法修完全部課程，回傳空陣列。

思考

什麼情況下會導致無法修完所有課程？考慮以下組合：

• prerequisites[0] = (1, 0)：修課程 1 之前必須修課程 0
• prerequisites[1] = (2, 1)：修課程 2 之前必須修課程 1
• prerequisites[2] = (0, 2)：修課程 0 之前必須修課程 2

轉成有向圖之後：

這三個條件形成了一個 cycle，導致永遠無法找到合法的修課起點。

這題本質上是圖論題：把先修條件建成有向圖，用 DFS 檢查是否有 cycle。偵測到 cycle 就回傳空陣列；沒有 cycle 則 DFS 的完成順序的反轉就是答案（拓樸排序）。

DFS 過程中用 status 記錄每個節點的狀態：0 代表未拜訪，1 代表正在拜訪（當前 DFS path 上），2 代表已完成。若 DFS 途中遇到 status[cur] == 1，代表有 cycle 存在。

解題紀錄

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        
        // 建立有向圖
        for (const auto &requisite: prerequisites) {
            graph[requisite[1]].push_back(requisite[0]);
        }
        
        vector<int> order;
		// 紀錄節點狀態
        vector<int> travel_status(numCourses, 0);
        
        for (int course = 0; course < numCourses; course++) {
            if (!dfs(course, graph, travel_status, order)) return {};
        }
        
        reverse(order.begin(), order.end());
        return order;
    }
    
    // If return ture, mean graph has cycle.
    bool dfs(int cur, vector<vector<int>> &graph, 
             vector<int> &status, vector<int> &order) {
        if (status[cur] == 1) return false;
        if (status[cur] == 2) return true;
        
        // 目前正在拜訪 cur 節點
        // 如果後續又再次 dfs 到 cur 節點，代表 cycle 存在 return false
        status[cur] = 1;
        
        for (const int target: graph[cur]) {
            if (!dfs(target, graph, status, order)) return false;
        }
        
        status[cur] = 2;
        order.push_back(cur);
        return true;
    }
};