Skip to main content

课程表

题目​

你这个学期必须选修 numCourses 门课程, 记为 0 到 numCourses - 1.

在选修某些课程之前需要一些先修课程. 先修课程按数组 prerequisites 给出, 其中 prerequisites[i] = [aᵢ, bᵢ], 表示如果要学习课程 aᵢ 则必须先学习课程 bᵢ.

  • 例如, 先修课程对 [0, 1] 表示: 想要学习课程 0, 你需要先完成课程 1.

请你判断是否可能完成所有课程的学习? 如果可以, 返回 true; 否则, 返回 false.

提示:
  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= aᵢ, bᵢ < numCourses
  • prerequisites[i] 中的所有课程对互不相同
示例
输入: numCourses = 2, prerequisites = [[1,0]]
输出: true
解释: 总共有 2 门课程. 学习课程 1 之前, 你需要完成课程 0. 这是可能的.
输入: numCourses = 2, prerequisites = [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程. 学习课程 1 之前, 你需要先完成​课程 0; 并且学习课程 0 之前, 你还应先完成课程 1. 这是不可能的.

题解​

这道题本质上是一个有向图的环检测问题.

  • 课程可以看作图中的节点.
  • 课程之间的依赖关系可以看作图中的有向边.
/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  const graph = Array(numCourses)
    .fill(null)
    .map(() => [])
  const inDegree = Array(numCourses).fill(0)

  // 构建邻接表
  for (const [course, pre] of prerequisites) {
    graph[pre].push(course)
    inDegree[course]++
  }

  const queue = []

  // 将入度为 0 的课程加入队列
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) {
      queue.push(i)
    }
  }

  let count = 0

  // 拓扑排序
  while (queue.length > 0) {
    const course = queue.shift()!
    count++

    for (const nextCourse of graph[course]) {
      inDegree[nextCourse]--
      if (inDegree[nextCourse] === 0) {
        queue.push(nextCourse)
      }
    }
  }

  return count === numCourses
}
  • 时间复杂度： O(V + E), 其中 V 是课程数量, E 是依赖关系数量.
  • 空间复杂度： O(V), 用于存储邻接表和访问标记数组.