课程表 II

最朴素的做法：每轮扫一遍所有课，挑还没学、且前置都学完的去学。可每轮都要把每门课的前置重新检查一次，n 门课最坏扫 n 轮——大量重复。

转折：与其每轮重数，不如给每门课维护入度（指向它的箭头数 = 还差几门前置）。入度 0 的先入队；每次出队一门课就追加进 order，再把它解锁的课入度各减 1，谁减到 0 才入队。这样每条边只用一次，order 收集的顺序就是拓扑序。

建图 + 算入度：邻接表 g[0]=[1,2]、g[1]=[3]、g[2]=[3]，数出入度：课 0 没前置(0)，课 1、2 各等一门(1)，课 3 等两门(2)。order 现在还空。

入度 0 先入队：把入度为 0 的课入队：只有课 0 没前置，先放进队列，作为「现在就能学」的起点。

出队 0 · 记入 order：取出 0 学完，第一时间把它追加进 order=[0]——出队顺序就是答案顺序。接着看它解锁了哪些课：g[0]=[1,2]。

0→1 减入度 → 归 0 入队：沿边 0→1，课 1 入度 1→0：它唯一的前置 0 学完了，立刻入队。

0→2 减入度 → 也归 0 入队：再沿边 0→2，课 2 入度也减到 0，入队。现在队列 [1,2] 都待学，0 处理完变绿。 队列里 1、2 谁先弹取决于入队次序，所以 [0,2,1,3] 等也是合法拓扑序——顺序和我不同不代表错。

出队 1 · 记入 order：取出 1 学完，追加进 order=[0,1]。它解锁课 3：g[1]=[3]。

1→3 减入度（负例：没归 0，不入队）：沿边 1→3，课 3 入度 2→1：还没到 0（还差课 2）——所以课 3 暂不入队。关键：减入度 ≠ 立即入队，只有归零才入队。

出队 2 · 记入 order：取出 2 学完，追加进 order=[0,1,2]。它也解锁课 3：g[2]=[3]。

2→3 减入度（这次归 0 → 入队）：沿边 2→3，课 3 入度 1→0：两门前置都学完了，入队。对比上一步——同样是减入度，这次归零所以入队。

出队 3 · 完成：取出 3 学完，order=[0,1,2,3]。长度 4 = 课程数 n，返回这个顺序 [0,1,2,3]。若图有环，环上的课入度永远减不到 0、进不了队，order 长度小于 n，就返回空数组。 反过来：若图里有环，环上的课入度永远减不到 0、进不了队，order 长度 ＜ n，就返回 [] 表示无法完成。

凡是「给一堆依赖关系排出可行执行顺序」都是拓扑排序：课程安排、任务调度、编译依赖、Excel 公式求值。

边界三连：三种边界先想清楚。

面试官常追问：三个高频追问，答法记牢。