207\. 课程表
# 207. 课程表 (opens new window)
# Description
Difficulty: 中等
Related Topics: 深度优先搜索 (opens new window), 广度优先搜索 (opens new window), 图 (opens new window), 拓扑排序 (opens new window)
你这个学期必须选修 numCourses
门课程,记为 0
到 numCourses - 1
。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites
给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi。
- 例如,先修课程对
[0, 1]
表示:想要学习课程0
,你需要先完成课程1
。
请你判断是否可能完成所有课程的学习?如果可以,返回 true
;否则,返回 false
。
示例 1:
输入:numCourses = 2, prerequisites = [[1,0]]
输出:true
解释:总共有 2 门课程。学习课程 1 之前,你需要完成课程 0 。这是可能的。
1
2
3
2
3
示例 2:
输入:numCourses = 2, prerequisites = [[1,0],[0,1]]
输出:false
解释:总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的。
1
2
3
2
3
提示:
- 1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
prerequisites[i]
中的所有课程对 互不相同
# Solution
Language: JavaScript
/**
* @param {number} numCourses
* @param {number[][]} prerequisites
* @return {boolean}
*/
let canFinish = function(numCourses, prerequisites) {
// 如果没有先决条件,即所有的课程均没有依赖关系
// 直接返回 true
if (prerequisites.length === 0) {
return true
}
// 维护入度表
let inDegree = new Array(numCourses).fill(0)
// 维护临接表
let adj = new Map()
for (let e of prerequisites) {
inDegree[e[0]]++
if(!adj.has(e[1])) adj.set(e[1], [])
let vEdge = adj.get(e[1])
vEdge.push(e[0])
}
let queue = []
// 首先加入入度为 0 的结点
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] === 0) {
queue.push(i)
}
}
while (queue.length > 0) {
// 从队首移除
var v = queue.shift()
// 出队一门课程
numCourses--
if(!adj.has(v)) continue
// 遍历当前出队结点的所有临接结点
for(let w of adj.get(v)) {
inDegree[w]--
if (inDegree[w] === 0) {
queue.push(w)
}
}
}
return numCourses === 0
}
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
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