跳到正文
第 207 题中等

课程表

Course Schedule

给出 n 门课和「先修某课才能修另一课」的限制，判断能否排出一个修完全部课程的顺序。

在力扣中练习

题目描述

你这个学期必须选修 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 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

 

提示：

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

解题思路

主解法

拓扑排序 · Kahn（BFS）

反复修掉入度为 0 的课，看最后能不能全部修完

逐条看先修关系很难判断能否全部完成。把先修课指向后续课，并记录每门课还有多少先修未完成；剩余入度为 0 的课，才允许进入队列。

自拟主例共 6 门课，依赖为 [[1,0],[2,0],[3,1],[4,3],[3,4]]。课程 5 独立，0 分叉到 1 和 2，3 与 4 互相等待。

分步图解

建图并统计入度；课程 5 独立，3 与 4 相互依赖。

先修 → 后续课
0
1
2
3
4
5
当前可修的课先进先出
← 队首出队队尾入队 ←
空队列
剩余入度 · 课程 → 未修先修数
0→0
1→1
2→1
3→2
4→1
5→0
1 / 4
修完一门课只减少其后续课程的入度，最后一个先修消失才可入队。

取出一门可修课程，就减少它指向的每门后续课程的入度。只有减到 0 才入队；仍缺一门先修时不能提前安排。所有课程都要建立节点，独立课程也不能遗漏。

分步图解

修完 1，更新它指向的课程；已修 3/6 门。

taken
3
先修 → 后续课
0
1
2
3
4
5
当前可修的课先进先出
← 队首出队队尾入队 ←
2front
剩余入度 · 课程 → 未修先修数
0→0
1→0
2→0
3→1
4→1
5→0
1 / 3
环外部分可以完成，最终仍需比较 taken 和课程总数。

本例能修完 0、5、1、2，但 3、4 始终有未满足依赖。队列为空仅表示当前无课可修，还必须比较 taken 是否等于总课程数；此处 4 不等于 6，返回 false。

时间 O(n + m)空间 O(n + m)

易错点

  • 边建反了：prerequisites[i] = [a, b] 是 b 先修，边必须是 b → a，入度加在 a 上。
  • 只用「队列是否为空」判结果，不记 taken —— 有环时队列也会空，但课没修完。
  • 漏掉从没在 prerequisites 里出现的孤立课程，初始化入队时它们也要一起进队。
对照解法

DFS · 三色标记判环

沿着依赖链往下走，走回链上的点就是环

另一种 O(V+E) 判环方式，适合学习递归中的访问状态；主解法使用入度与队列。

DFS 的思路是「顺着一条依赖链往下走，如果走回了自己，就说明有环」。

用三种状态标记每个节点：

  • 0：还没访问过；
  • 1：正在当前的递归链上（在栈里）；
  • 2：已经确认它后面没有环。

从每个未访问的点出发 DFS：遇到状态 1 的邻居，说明沿着依赖链绕回了自己，立刻返回 false；遇到 0 就继续往下；一个点的所有邻居都走完且没发现环，就把它标成 2。

状态 2 很关键：它让每个点最多被完整展开一次，复杂度保持 O(n + m)。如果只用一个布尔值记「访问过」，就分不清遇到的是祖先（有环）还是别的分支（无环），会误报。

  1. 1从每个未访问的课程出发 DFS。
  2. 2进入 u 时标记 state[u] = 1。
  3. 3遍历 u 的后继：遇到 state = 1 说明成环，返回 false。
  4. 4遇到 state = 0 的继续递归。
  5. 5u 的全部后继都安全，标记 state[u] = 2 并返回 false（无环）。
时间 O(n + m)空间 O(n + m)

易错点

  • 用 bool visited 代替三色标记，会把「指向其他分支」误判成环。
  • 忘记在 DFS 结束后把 state 改成 2，同一个点会被反复展开，复杂度退化。
  • 递归深度最多 n = 2000，这个规模安全；再大要考虑改成显式栈。

代码与演示

主解法配有图解；对照解法用于比较思路、复杂度或实现方式。

演示输入numCourses = 6, prerequisites = [[1,0],[2,0],[3,1],[4,3],[3,4]]

建图并统计入度；课程 5 独立，3 与 4 相互依赖。

先修 → 后续课
0
1
2
3
4
5
当前可修的课先进先出
← 队首出队队尾入队 ←
空队列
剩余入度 · 课程 → 未修先修数
0→0
1→1
2→1
3→2
4→1
5→0
1 / 7
查看 C++ 代码

延伸阅读

  • Kahn 算法的出队顺序本身就是一个合法拓扑序 —— 课程表 II（210）只要把出队的课程记下来即可。
  • 有向图判环有两条等价路线：Kahn 计数看「有没有剩余点」，DFS 三色看「有没有回边」。
  • 无向图判环用并查集或 DFS 带父亲，不能套用入度：无向边的两端都会互相加度数。