-
Notifications
You must be signed in to change notification settings - Fork 70
/
Copy pathres.js
79 lines (71 loc) · 2.26 KB
/
res.js
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
/**
* res.js
* @authors Joe Jiang ([email protected])
* @date 2017-04-17 00:09:34
*
* Topological sorting: https://en.wikipedia.org/wiki/Topological_sorting
*
* There are a total of n courses you have to take, labeled from 0 to n - 1.
*
* Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
*
* Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
*
* For example:
*
* 2, [[1,0]]
* There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
*
* 2, [[1,0],[0,1]]
* There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
*
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
let canFinish = function(numCourses, prerequisites) {
let prelen = prerequisites.length,
maxNoCircle = numCourses * (numCourses - 1) / 2;
if (!prelen) {
return true;
} else if (prelen > maxNoCircle) {
return false;
}
let flags = [], // 存储未访问节点
nodemarks = new Array(numCourses), // 存储node访问标记
edges = new Array(numCourses); // 存储连边信息
for (let i = 0; i < numCourses; i++) {
flags.push(i);
nodemarks[i] = 0;
edges[i] = [];
}
for (let i = 0; i < prelen; i++) {
let source = prerequisites[i][0],
target = prerequisites[i][1];
edges[target].push(source);
}
while (flags.length) {
let node = flags[flags.length - 1];
if (!dfsVisit(node)) {
return false;
}
flags.pop();
}
return true;
function dfsVisit(node) {
if (nodemarks[node]) {
return false;
}
if (flags.indexOf(node) !== -1) {
nodemarks[node] = 1;
let elen = edges[node].length;
for (let i = 0; i < elen; i++) {
if (!dfsVisit(edges[node][i])) {
return false;
}
}
nodemarks[node] = 0;
}
return true;
}
};