题型地图 56天全屏 141题

当前：LC210 · 课程表 II / Course Schedule II · 首次出现于 Day 31 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

83 / 141回到 Day 31 卡片 141 题索引

LC210

课程表 II · 拓扑排序动画教学页

从课程依赖到 result 数组：用 Kahn BFS 排出一条可执行学习顺序

深色工程执行实验室风：先读懂 prerequisites 的人话含义，再同步观察 graph、indegree、queue、result 四个状态如何推进。

Kahn BFS[a,b] = b -> a返回课程顺序

from problem

题目在问什么

LC210 不是只判断能不能学完，而是要求返回一条真的能照着学的课程顺序。输入里有课程数量和先修关系，输出要是一个数组，比如 [0,1,2,3]。

prerequisites[i] = [a,b] 的意思是：想学 a，必须先学 b。所以建图方向是 b -> a。

示例：numCourses = 4，prerequisites = [[1,0], [2,0], [3,1], [3,2]]，合法答案：[0,1,2,3] 或 [0,2,1,3]。

LC207 返回 true/false

只问“能不能完成所有课程”，不用输出具体顺序。

LC210 返回一个具体的课程学习顺序

不仅要判断没有环，还要把每次学到的课程放进 result。

to model

完整建模过程

课程 = 图节点	每门课 0、1、2、3 都是图里的一个点。
先修关系 = 有向边	箭头从先学的课指向被解锁的课。
indegree[i] = 课程 i 还剩几个前置课程没完成	值为 0 才能进入 queue。
queue = 当前可以学习的课程	从左侧弹出，表示真的开始学这门课。
result = 已经排好的学习顺序	最后要返回这个数组，而不是 true。

lab layout

工程执行实验室

左侧展示课程依赖图

看节点颜色和箭头方向，确认谁解锁谁。

中间展示动画执行

每一步都有一句人话解释，先看动作再看变量。

右侧展示状态面板

固定盯住当前步骤、queue、result、indegree、当前处理的边。

cycle case

有环失败示例

numCourses = 2

prerequisites = [[1,0], [0,1]]

0 -> 1

1 -> 0

0 和 1 互相依赖：0 等 1，1 也等 0。

一开始没有入度为 0 的课程，queue 为空，result 长度小于 numCourses，最后返回 []。

边界测试 · 切换后整段动画会重算

帧 1/8Scene 1

灰色：还不能学习蓝色：入度为 0，当前可学习绿色：已经加入 result红色：有环失败示例中的循环节点

课程依赖图 graph

graph[0][]

graph[1][]

graph[2][]

graph[3][]

中间展示动画执行

Step 1：展示原始输入

人话：不是只判断能不能学完，而是要真的给出一张课程表。

合法答案：[0,1,2,3] 或 [0,2,1,3]，因为 1 和 2 都只依赖 0。

queue

[]

result

[]

先别急着说拓扑排序。题目给 numCourses = 4 和 prerequisites = [[1,0], [2,0], [3,1], [3,2]]，要我们排出一条可行学习顺序。

右侧展示状态面板

当前步骤

Step 1：展示原始输入

queue

[]

result

[]

indegree

课 0

课 1

课 2

课 3

当前处理的边 currentEdge

无

时间线 · 点击跳转

代码 · 当前高亮行随帧切换

1func findOrder(numCourses int, prerequisites [][]int) []int {
2    graph := make([][]int, numCourses)
3    indegree := make([]int, numCourses)
4 
5    for _, p := range prerequisites {
6        a, b := p[0], p[1]
7        graph[b] = append(graph[b], a)
8        indegree[a]++
9    }
10 
11    queue := make([]int, 0)
12 
13    for i := 0; i < numCourses; i++ {
14        if indegree[i] == 0 {
15            queue = append(queue, i)
16        }
17    }
18 
19    result := make([]int, 0, numCourses)
20 
21    for len(queue) > 0 {
22        cur := queue[0]
23        queue = queue[1:]
24 
25        result = append(result, cur)
26 
27        for _, next := range graph[cur] {
28            indegree[next]--
29 
30            if indegree[next] == 0 {
31                queue = append(queue, next)
32            }
33        }
34    }
35 
36    if len(result) != numCourses {
37        return []int{}
38    }
39 
40    return result
41}

complexity

时间复杂度：O(V + E)

建图遍历 E 条依赖，Kahn BFS 中每门课和每条边都只处理一次，所以时间复杂度是 O(V + E)。

空间复杂度：O(V + E)

邻接表 graph 存 E 条边，indegree、queue、result 都和 V 同级，所以空间复杂度是 O(V + E)。

V 是课程数量，E 是依赖关系数量。

当前用例：主例 · 排出顺序 · 等待把输入翻译成依赖图

常见误区

把 [a,b] 画成 a -> b，会把学习顺序反过来。
LC207 返回 true/false，LC210 返回一个具体的课程学习顺序。
拓扑序不唯一，[0,1,2,3] 或 [0,2,1,3] 都合法。
queue 为空时不能直接返回 result，还要检查 result 长度是否等于 numCourses。
indegree[next]-- 后只有变成 0 才能入队。

面试怎么说

这题是拓扑排序。
用 Kahn BFS。
建图时 [a,b] 表示 b -> a。
indegree 记录每门课还有几个前置条件。
每次取出入度为 0 的课程加入结果。
如果最后 result 长度等于 numCourses，返回 result；否则说明有环，返回空数组。