-
Notifications
You must be signed in to change notification settings - Fork 0
/
LC210courseSchedule.cpp
39 lines (37 loc) · 1.26 KB
/
LC210courseSchedule.cpp
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
34
35
36
37
38
39
#include <map>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
map<int, vector<int>> G;
vector<int> visited(numCourses, -1);
for (int i = 0; i < prerequisites.size(); i++) {
G[prerequisites[i][1]].push_back(prerequisites[i][0]);
visited[prerequisites[i][0]] = 0;
}
vector<int> res;
if (!dfs(G, visited, res) || res.size() < numCourses) res.clear();
reverse(res.begin(), res.end());
return res;
}
private:
bool dfs(map<int, vector<int>>& G, vector<int>& visited, vector<int>& res) {
for (int i = 0; i < visited.size(); i++)
if (visited[i] == -1 && !dfs_visit(G, i, visited, res))
return false;
return true;
}
bool dfs_visit(map<int, vector<int>>& G, int u, vector<int>& visited,
vector<int>& res) {
visited[u] = 1;
for (int i = 0; i < G[u].size(); i++) {
if (visited[G[u][i]] == 1) return false;
if (visited[G[u][i]] <= 0 && !dfs_visit(G, G[u][i], visited, res))
return false;
}
visited[u] = 2;
res.push_back(u);
return true;
}
};