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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153 | //C++: method1 740ms label the courses along the recursion
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<int> label(numCourses), ret;
bool visited[2000] = {false};
int cur_label = numCourses;
for(int i=0; i<numCourses; ++i){
if(!visited[i]) dfs(i, prerequisites, visited, label, cur_label, ret);
}
for(auto p:prerequisites){
if(label[p.first]<label[p.second]){
return vector<int>();
}
}
reverse(ret.begin(), ret.end());
return ret;
}
void dfs(int course, vector<pair<int, int>>& prerequisites, bool *visited, vector<int> &label, int &cur_label, vector<int> &ret){
visited[course] = true;
for(auto p:prerequisites){
if(course==p.second && !visited[p.first]){
dfs(p.first, prerequisites, visited, label, cur_label, ret);
}
}
label[course] = --cur_label;
ret.push_back(course);
}
};
//C++: method2 524ms standard dfs method using a stack
#define NC 2000
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
bool preqs[NC][NC] = {false};
for(auto p:prerequisites) preqs[p.second][p.first] = true;
bool visited[NC] = {false};
bool path[NC] = {false};
stack<int> stk;
vector<int> ret;
for(int i=0; i<numCourses; ++i){
if(!visited[i]){
path[i] = true;
if(hasCycle(numCourses, i, stk, preqs, visited, path)) return ret;
path[i] = false;
}
}
while(!stk.empty()){
ret.push_back(stk.top());
stk.pop();
}
return ret;
}
bool hasCycle(int N, int node, stack<int> &stk, bool preqs[][NC], bool *visited, bool *path){
visited[node] = true;
for(int i=0; i<N; ++i){
if(preqs[node][i]){
if(path[i]) return true;
path[i] = true;
if(!visited[i]) if(hasCycle(N, i, stk, preqs, visited, path)) return true;
path[i] = false;
}
}
stk.push(node);
return false;
}
};
//C++: method3 620ms dfs method without a stack
class Solution {
public:
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<int> order;
bool visited[numCourses];
memset(visited, false, numCourses*sizeof(bool));
bool path[numCourses];
memset(path, false, numCourses*sizeof(bool));
for(int i=0; i<numCourses; ++i){
path[i] = true;
if(!visited[i] && hasCycle(numCourses, prerequisites, i, visited, path, order)){
order.clear();
return order;
}
path[i] = false;
}
reverse(order.begin(), order.end());
return order;
}
bool hasCycle(int numCourses, vector<pair<int, int>>& prerequisites, int curNode, bool *visited, bool *path, vector<int> &order){
visited[curNode] = true;
for(auto p:prerequisites){
if(p.second==curNode){
if(path[p.first]) return true;
if(!visited[p.first]){
path[p.first] = true;
if(hasCycle(numCourses, prerequisites, p.first, visited, path, order))
return true;
path[p.first] = false;
}
}
}
order.push_back(curNode);
return false;
}
};
//Java
class Solution {
Set<Integer> path, visited;
Map<Integer, Set<Integer>> preqs;
List<Integer> schedule;
public int[] findOrder(int numCourses, int[][] prerequisites) {
path = new HashSet<>();
visited = new HashSet<>();
preqs = new HashMap<>();
schedule = new ArrayList<>();
for(int[] p : prerequisites){
preqs.computeIfAbsent(p[0], k -> new HashSet<Integer>()).add(p[1]);
}
for(int c = 0; c<numCourses; ++c){
path.add(c);
if(!visited.contains(c) && hasCycle(c))
return new int[0];
path.remove(c);
}
int[] ret = new int[schedule.size()];
for(int i=0; i<schedule.size(); ++i) ret[i] = schedule.get(i);
return ret;
}
boolean hasCycle(int course){
visited.add(course);
if(preqs.containsKey(course)){
for(int p : preqs.get(course)){
if(path.contains(p)) return true;
path.add(p);
if(!visited.contains(p) && hasCycle(p)) return true;
path.remove(p);
}
}
schedule.add(course);
return false;
}
}
|
