Skip to main content

课程表-ii

Tips

题目类型: Graph

题目​

现在你总共有 numCourses 门课需要选, 记为 0 到 numCourses - 1. 给你一个数组 prerequisites , 其中 prerequisites[i] = [aᵢ, bᵢ], 表示在选修课程 aᵢ 前必须先选修 bᵢ.

  • 例如, 想要学习课程 0, 你需要先完成课程 1, 我们用一个匹配来表示: [0,1].

返回你为了学完所有课程所安排的学习顺序. 可能会有多个正确的顺序, 你只要返回任意一种就可以了. 如果不可能完成所有课程, 返回一个空数组.

提示:
  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= aᵢ, bᵢ < numCourses
  • aᵢ != bᵢ
  • 所有 [aᵢ, bᵢ] 互不相同
示例
输入: numCourses = 2, prerequisites = [[1,0]]
输出: [0,1]
解释: 总共有 2 门课程. 要学习课程 1, 你需要先完成课程 0. 因此, 正确的课程顺序为 [0,1] .
输入: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出: [0,2,1,3]
解释: 总共有 4 门课程. 要学习课程 3, 你应该先完成课程 1 和课程 2. 并且课程 1 和课程 2 都应该排在课程 0 之后.
因此, 一个正确的课程顺序是 [0,1,2,3] . 另一个正确的排序是 [0,2,1,3] .
输入: numCourses = 1, prerequisites = []
输出: [0]

题解​

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = 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)
    }
  }

  const result = []

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

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

  return result.length === numCourses ? result : []
}