跳到主要内容

LeetCode 210. 课程表 II

本节目标

在 Kahn 拓扑排序中记录出队课程，构造任意合法的先修顺序。

这是有向依赖与拓扑排序中“构造一个顺序”的母题。可用性判断与课程表相同，区别仅在于每次从队列取出的课程都要写入答案。

查看 LeetCode 原题

题意与约束​

返回任意一个满足所有先修关系的课程顺序；若存在环，返回空数组。题目允许多种答案：两个当前入度均为 0 的课程谁先出队都合法。测试因此验证“每门课恰好一次且每条先修边前后关系正确”，而不把某个偶然的队列顺序写死。

直接思路与瓶颈​

若每次都从全部课程中重新寻找“其所有前置都已写入答案”的课程，需要反复检查先修对；在长链或大量共享前置时会产生 O(nm) 的重复判断。先随意排列课程再验证也无法在遇到环时构造合法顺序。

图模型与算法推导​

建立 before → course 和 indegree[course] 后，先将所有零入度课程入队。循环中把出队课程追加到 order，再减少其后继入度。只要 order 长度最终为总课程数，order 中每条边的起点都已在终点前被追加，因此它是拓扑序。

若环阻塞了剩余课程，队列会提前为空，order 只是一个合法前缀而不是完整解，必须丢弃并返回空数组。

正确性依据​

每次追加的课程入度为 0，故在它之前所有先修都已追加；所以答案前缀始终合法。后继只有在最后一个先修被处理后才入队，保持这一性质。若最终长度为 n，每个顶点恰好一次且所有边方向正确；若长度不足，按 Kahn 算法的剩余入度论证，未处理部分含环，无合法拓扑序。故算法返回值正确。

样例执行过程​

取 numCourses = 4，prerequisites = [[1,0],[2,0],[3,1],[3,2]]。初始 indegree = [0,1,1,2]、ready = [0]、order = []。弹出 0 后 order = [0]，将 1、2 降到零入度，队列变为 [1,2]。随后弹出 1，order = [0,1]、3 的入度为 1；弹出 2 后 order = [0,1,2]、3 入队；最后弹出 3 得 order = [0,1,2,3]。长度为 4，所以返回这一顺序；若另加先修对 [0,3]，所有课程都无法以零入度入队，最终返回空数组。

代码实现​

C++17
#include <queue>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses, 0);
        for (const auto& prerequisite : prerequisites) {
            int course = prerequisite[0];
            int before = prerequisite[1];
            graph[before].push_back(course);
            indegree[course]++;
        }

        queue<int> ready;
        for (int course = 0; course < numCourses; course++) {
            if (indegree[course] == 0) ready.push(course);
        }

        vector<int> order;
        while (!ready.empty()) {
            int course = ready.front();
            ready.pop();
            order.push_back(course);
            for (int nxt : graph[course]) {
                if (--indegree[nxt] == 0) ready.push(nxt);
            }
        }
        return static_cast<int>(order.size()) == numCourses ? order : vector<int>{};
    }
};

两份实现均在 Kahn 循环内追加答案。行为测试刻意给出多个同时可选的起点，并用位置映射检查所有先修边，不要求唯一顺序。

复杂度分析​

建图与处理各扫描一次顶点和边，时间复杂度 O(n + m)；邻接表、入度、队列和答案使用 O(n + m) 额外空间。

边界与易错点​

  • 返回 order 前必须确认长度为 numCourses。
  • 不要把入度数组直接当作答案；它只记录未完成先修数量。
  • 独立课程也要入队并写入结果。
  • 多个合法序并不意味着实现不稳定，除非题目额外要求字典序最小。

模式迁移​

任何“给出一个可行执行序列”的依赖题都可复用该模板。若每一步还要选择最小编号，队列替换成最小堆即可，正确性不变而取序规则改变。