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