Open xszi opened 3 years ago
题解来自瓶子君课程表问题
拓扑排序(有向无环图)
使用广度优先遍历
例如:
输入: 5, [[4,2],[4,3],[2,0],[2,1]]
使用 邻接表 来表示有向图中各个节点的依赖关系,同时维护一个入度表,则入度表中入度为 0 的节点所表示的课程是可以立即开始学习的(没有先决条件条件或先觉条件已完成)
所以:
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
}
你这个学期必须选修 numCourse 门课程,记为 0 到
numCourse-1
。在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]
给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?
示例 1:
示例 2:
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。
提示:
1 <= numCourses <= 10^5
leetcode