LeetCode 210. Course Schedule II

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
24
class Solution {
public:
    vector<int> findOrder(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);
        vector<int> ans;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            ans.push_back(u);
            for (int v: edges[u])
                if (--indeg[v] == 0)
                    q.push(v);
        }
        return ans.size() == numCourses ? ans : vector<int>();
    }
};
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
30
31
32
33
class Solution {
public:
    vector<int> findOrder(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);
        if (!valid) return vector<int>();
        reverse(ans.begin(), ans.end());
        return ans;
    }
private:
    vector<vector<int>> edges;
    vector<int> visited;
    vector<int> ans;
    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;
        ans.push_back(u);
    }
};