LeetCode 207. Course Schedule

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edges(numCourses, vector<int>());
        vector<int> indeg(numCourses, 0);
        for (const auto& info : prerequisites) {
            edges[info[1]].push_back(info[0]);
            ++indeg[info[0]];
        }
        queue<int> q;
        for (int i = 0; i < numCourses; ++i)
            if (indeg[i] == 0)
                q.push(i);
        while (!q.empty()) {
            --numCourses;
            int u = q.front(); q.pop();
            for (int v : edges[u])
                if (--indeg[v] == 0)
                    q.push(v);
        }
        return numCourses == 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        edges.resize(numCourses);
        visited.resize(numCourses);
        for (const auto& info: prerequisites)
            edges[info[1]].push_back(info[0]);
        for (int i = 0; i < numCourses && valid; ++i)
            if (visited[i] == 0)
                dfs(i);
        return valid;
    }
private:
    vector<vector<int>> edges;
    vector<int> visited;
    bool valid = true;
    void dfs(int u) {
        visited[u] = 1;
        for (int v: edges[u])
            if (visited[v] == 0) {
                dfs(v);
                if (!valid) return;
            } else if (visited[v] == 1) {
                valid = false;
                return;
            }
        visited[u] = 2;
    }
};