210. Course Schedule II

題目網址：https://leetcode.cn/problems/course-schedule-ii/

題意：你這學期必須選修 numCourses 門課程, 標記為 0 到 numCourses - 1。

在修習某些課程前需要一些先修課程 prerequisites, 其中 prerequisites[i] = [a_i, b_i], 表示要修 a_i 前必須先修 b_i。

• e.g. [0, 1] 表示想要修課程 0, 需要先完成課程 1。

返回能夠學習完所有可成的學習順序。可能會有很多種正確的順序, 只要返回其中一種就行。若不可能完成所有課程, 則返回空 list。

Solution 1：

想法：利用 Topological Sort + BFS, 同 207. Course Schedule

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> inDegree(numCourses, 0); // 紀錄每個 node 的 in degree
        vector<vector<int>> adj(numCourses); // adjacent list

        for (const auto& pre : prerequisites) {
            adj[pre[1]].emplace_back(pre[0]);
            ++inDegree[pre[0]];
        }

        // 先將 in degree = 0 的 node 加入到 queue 中
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (inDegree[i] == 0) { 
                q.emplace(i);
            }
        }

        // bfs
        vector<int> res;
        while (!q.empty()) {
            const auto cur = q.front();
            q.pop();
            res.emplace_back(cur);

            // 將其 adjacent node 的 in degree - 1
            for (const auto& v : adj[cur]) {
                if (--inDegree[v] == 0) {
                    q.emplace(v);
                }
            }
        }
        return (res.size() == numCourses) ? res : vector<int>();
    }
};

• time：$O(n + m)$ ➔ n 為課程數(vertex), m 為先修課程數(edge)。其實就是對圖進行 BFS 所需之時間複雜度 $O(V+E)$
• space：$O(n + m)$ ➔ 因為 adj 為 $O(V+E)$, V 是因為要記錄所有點, E 是因為會記錄所有邊

Solution 2：

想法：利用 Topological Sort + DFS, 同 207. Course Schedule

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses); // adjacency list
        for (const auto& pre : prerequisites) {
            adj[pre[0]].emplace_back(pre[1]);
        }

        // 0: 未搜索, 1: 搜索中, 2: 已搜索
        vector<int> states(numCourses, 0);
        for (int i = 0; i < numCourses; ++i) {
            if (dfs(i, states, adj)) {
                return {};
            }
        }

        return res;
    }

private:
    vector<int> res;

    // 返回 true 代表有 cycle
    bool dfs(const int i, vector<int>& states, vector<vector<int>>& adj){
        // 當前 node 狀態為搜索中, 代表有 cycle
        if (states[i] == 1) {
            return true;
        }

        // 當前 node 狀態為已搜索, 代表沒 cycle
        if (states[i] == 2) {
            return false;
        }

        states[i] = 1; // 若為未搜索, 將其設為搜索中

        // dfs 遍歷其 adjacent node
        for (const auto& v : adj[i]) {
            if (dfs(v, states, adj)) {
                return true;
            }
        }

        states[i] = 2; // 設為已完成
        res.emplace_back(i); // push 到 order list 中

        return false;
    }
};

• time：$O(n + m)$ ➔ n 為課程數(vertex), m 為先修課程數(edge)。其實就是對圖進行 DFS 所需之時間複雜度 $O(V+E)$
• space：$O(n + m)$ ➔ 因為 adj 為 $O(V+E)$, V 是因為要記錄所有點, E 是因為會記錄所有邊