207. Course Schedule

---

My Solution

Solution 1: Topological Sort

The Key Idea for Solving This Coding Question

C++ Code

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses, 0);
        for (auto &e : prerequisites) {
            graph[e[1]].push_back(e[0]);
            ++indegree[e[0]];
        }

        queue<int> q;
        for (int i = 0; i < indegree.size(); ++i) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int curr = q.front();
            q.pop();

            for (auto &next : graph[curr]) {
                --indegree[next];
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
            --numCourses;
        }

        return numCourses == 0;
    }
};

Time Complexity

Space Complexity

Solution 2: DFS (detect cycle)

The Key Idea for Solving This Coding Question

C++ Code

#define WHITE (0)
#define GRAY  (1)
#define BLACK (2)

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
        vector<vector<int>> graph(numCourses);
        for (auto &e : prerequisites) {
            graph[e[1]].push_back(e[0]);
        }

        vector<int> state(numCourses, WHITE);
        for (int curr = 0; curr < numCourses; ++curr) {
            if (state[curr] == WHITE && hasCycle(graph, state, curr)) {
                return false;
            }
        }
        return true;
    }

private:
    bool hasCycle(vector<vector<int>> &graph, vector<int> &state, int curr) {
        state[curr] = GRAY;
        for (auto &next : graph[curr]) {
            if (state[next] == GRAY) {
                // A cycle is detected.
                return true;
            }
            if (state[next] == BLACK) {
                // We have visited next and all its descendants.
                continue;
            }
            if (hasCycle(graph, state, next)) {
                // A cycle has been detected in the descendants.
                return true;
            }
        }
        state[curr] = BLACK;

        return false;
    }
};

Time Complexity

Space Complexity

Miscellaneous

210. Course Schedule II