跳到主要内容

LeetCode 207. 课程表

本节目标

用 Kahn 拓扑排序统计可处理课程，判断先修依赖是否含环。

这是有向依赖与拓扑排序中“能否完成全部任务”的母题。[a, b] 的意思是先完成 b 才能学习 a，因此必须建立 b → a，而不是照数组顺序建边。

查看 LeetCode 原题

题意与约束​

给定 numCourses 门课程和先修对，判断是否能修完全部课程。没有任何先修关系时，所有课程都可立刻开始；环如 0 → 1 → 0 则让环中课程都永远无法满足前置条件。图也可能有多个互不相连的依赖组，初始化时必须把每个入度为 0 的课程都入队。

直接思路与瓶颈​

可以不断扫描全部先修对，寻找“前置课程已经完成”的课程并标记完成。这个做法每完成一门课都可能重扫 m 条边；长度为 n 的依赖链会导致 O(nm) 的重复检查，也不容易准确识别已经再无可选课程的环。

图模型与算法推导​

indegree[x] 始终表示“在尚未处理的课程中，还欠多少条指向 x 的先修边”。队列中的课程入度都为 0，所以任意出队课程都可以合法完成。完成它后，只有它的后继课程少一个前置条件；后继入度降为 0 的瞬间才入队。

若最终处理数为 numCourses，每门课程都曾在前置条件满足后被取出。反之，若队列空了仍有未处理课程，剩余部分不存在入度为 0 的点，必含有向环，不能完成。

正确性依据​

队列初始化纳入所有无前置课程，基础状态正确。每次取出入度为 0 的课程，不会违反任何先修边；对它每条出边减一次入度，恰好反映“该前置已完成”，因而不变量保持。所有课程均被处理时得到一条合法完成过程；无法继续处理时剩余点至少互相依赖形成环。故返回处理数是否等于总课程数正确。

样例执行过程​

取 numCourses = 4，prerequisites = [[1,0],[2,0],[3,1],[3,2]]。建图为 0 → {1,2}、1 → 3、2 → 3，初始 indegree = [0,1,1,2]，ready = [0]。出队 0 后 processed = 1，1、2 的入度均减为 0，队列为 [1,2]。出队 1 后 3 的入度从 2 到 1；出队 2 后 3 变为 0，队列为 [3]。最后出队 3，processed = 4，等于课程数，返回 true。

代码实现​

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

class Solution {
public:
    bool canFinish(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);
        }

        int processed = 0;
        while (!ready.empty()) {
            int course = ready.front();
            ready.pop();
            processed++;
            for (int nxt : graph[course]) {
                if (--indegree[nxt] == 0) ready.push(nxt);
            }
        }
        return processed == numCourses;
    }
};

行为测试同时覆盖一条链、一个二元环和空依赖。C++ 与 Python 都只维护邻接表、入度和 FIFO 队列，不依赖某个特定课程编号的遍历顺序。

复杂度分析​

每门课程入队、出队至多一次，每条先修边只检查一次，时间复杂度 O(n + m)；邻接表、入度和队列合计额外空间 O(n + m)。

边界与易错点​

  • [course, before] 应建 before → course，并增加 course 的入度。
  • 初始队列要扫描全部课程，不能只从 0 开始。
  • 空先修表返回真，即使课程数大于一。
  • 不能仅凭“曾弹出一个点”判断无环，必须比较处理数。

模式迁移​

如果题目要求输出具体安排，在相同出队循环中收集课程，见下一题。若还要算每门任务的最早完成时间，可把时间状态沿拓扑边向后松弛。