-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCourseScheduleII.js
More file actions
62 lines (56 loc) · 1.98 KB
/
Copy pathCourseScheduleII.js
File metadata and controls
62 lines (56 loc) · 1.98 KB
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
// https://leetcode-cn.com/problems/course-schedule-ii/
var Test = require('../Common/Test');
var findOrder = function (numCourses, prerequisites) {
const graph = createGraph(numCourses, prerequisites);
return findOrderDFS(graph);
function createGraph(numCourses, prerequisites) {
const graph = Array.from({ length: numCourses }, () => []);
for (const [start, target] of prerequisites) {
graph[start].push(target);
}
return graph;
}
function findOrderDFS(graph) {
const order = [];
const onStack = Array.from({ length: numCourses }, () => false);
const visited = Array.from({ length: numCourses }, () => false);
const stack = [];
for (let i = 0; i < numCourses; i++) {
if (!visited[i]) {
visited[i] = true;
onStack[i] = true
stack.push([i, 0]);
while (stack.length) {
const [v, index] = top = stack[stack.length - 1];
const ws = graph[v];
if (index < ws.length) {
top[1]++;
const w = ws[index];
if (onStack[w]) {
return [];
}
else {
if (!visited[w]) {
onStack[w] = true;
visited[w] = true;
stack.push([w, 0]);
}
}
}
else {
order.push(v);
onStack[v] = false;
stack.pop();
}
}
}
}
return order;
}
};
function test(numCourses, prerequisites) {
Test.test(findOrder, numCourses, prerequisites);
}
// test(2, [[1, 0]]);
// test(4, [[1, 0], [2, 0], [3, 1], [3, 2]]);
test(2, [[0, 1]]);