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

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

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

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

返回是否能完成所有課程。

Solution 1：

想法：利用 Topological Sort + BFS, 依序取出 inDegree = 0 之 node

在 BFS 中, [0, 1] 表示想要修課程 0, 需要先完成課程 1。
用圖表示為 1 指向 0（方向跟 DFS 相反）, 這樣 1 的 inDegree = 0, 才會優先被執行

  • 首先將 inDegree = 0 的 node（不需要任何先修課程的課）加入到 queue 中
  • BFS
    • 取出 queue.front() 後, 將其相鄰 node 的 inDegree - 1
    • 若相鄰 node 之 inDegree - 1 後為 0, 則將該 node push 到 queue 中
  • 特殊情況：若 Graph 有 cycle

    • 不會有任何 node 加入到 queue 中（所有 node 之 inDegree 皆不為 0）, 故要用一變數 visited 紀錄 inDegree = 0 的個數

    • 當 queue 取出 front 時 visited + 1, 因為 queue 中的 node 一定是 inDegree = 0 的 node

    • 最後判斷 visited 是否等於 numCourses

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

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

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

        int visited = 0;
        while (!q.empty()) {
            const auto cur = q.front();
            q.pop();

            ++visited;

            // 將其 adjacent node 的 in degree - 1
            for (const auto& v : adj[cur]) {
                if (--inDegree[v] == 0) {
                    q.emplace(v);
                }
            }
        }
        return visited == numCourses;
    }
};
  • 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, 其實本題就是在問有向圖中是否有 cycle。此外也要考慮存在 isolated node 的情況（也就是 Graph 非 connected, 如下圖中的 3）

e.g. 下圖中 (0, 1, 5) 為 cycle, 故返回 false

在 DFS 中, [0, 1] 表示想要修課程 0, 需要先完成課程 1。用圖表示為 0 指向 1

class Solution {
public:
    bool canFinish(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) { // 讓 isolated node 也能被搜索
            if (dfs(i, states, adj)) { 
                return false;
            }
        }

        return true;
    }

private:
    // 返回 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; // 設為已完成

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