课程表 图解题解

课程表这道题真正在问什么

共 numCourses 门课，prerequisites 里每一对 [b, a] 表示修 b 之前必须先修 a，问能否把所有课修完。把每门课看作节点、每条先修关系看作从 a 指向 b 的有向边（先修指向后修），问题就翻译成：这张有向图能否排出一个不违反任何箭头的线性顺序。答案取决于一件事——图里有没有环：课程互相等待形成死锁，谁都修不了；无环则一定存在合法顺序。所以这题真正问的是「有向图判环」。

为什么想到拓扑排序和入度

顺着生活直觉走：制定学习计划时，第一批修的必然是「没有任何先修要求」的课。翻译到图上，就是入度为 0 的节点——入度指有几条边指向它，也就是它还剩几门先修没满足。

修完一门课，它对后继课的约束就解除了，相当于把它的出边全部擦掉，后继课的入度各减一；谁的入度减到 0，谁就获得了「可以修」的资格。反复执行「取一门入度 0 的课修掉、给后继减入度」，就是 Kahn 算法的 BFS 拓扑排序：用队列装着当前所有可修的课，出队一门、松动一批，直到队列耗尽。

队列维护的不变量与每步的正确性

整个过程保持一条不变量：队列里的课，先修要求全部已被修掉，随时可修。出队修掉它不会违反任何约束；给后继入度减一，则如实记录「又一门先修被满足」。每门课恰好在入度归零那一刻入队一次，每条边恰好在起点被修掉时处理一次，既不重复也不遗漏。

建图方向是最高频的错误：[b, a] 要建 a 指向 b 的边、给 b 的入度加一。方向一反，整个先修关系颠倒，拓扑序全错。记住口诀「先修指向后修」即可。

为什么用修课计数判环而不是看队列空

队列空只说明「没有课可修了」，不说明「课都修完了」。若图里有环，环上每门课都在等环上另一门课先修完，入度永远大于 0，一辈子进不了队——队列会提前耗尽，而这些课一门也没修掉。所以必须数一数总共出队了多少门课：计数等于 numCourses 才是真的全部修完（无环），小于则说明剩下的课困在环里，返回 false。

顺带一提，简单的 visited 标记判不出有向环，要么像这样用入度加计数，要么改用 DFS 三色标记法：搜索中遇到「正在访问中」的灰色节点，说明走回了当前路径，即有环。

复杂度怎么数，还有哪些变体

时间 O(V+E)：V 门课每门入队出队至多一次，E 条边在起点出队时各处理一次；空间 O(V+E)，花在邻接表、入度数组和队列上。

两个延伸：LeetCode 210 要求给出一个合法学习顺序，做法完全一样，把每次出队的课依次记进数组，最后长度够就返回它；另外若输入含重复的先修边，入度会被多算导致误判，健壮的做法是建图时先对边去重。

Python

from collections import deque
def canFinish(numCourses, prerequisites):
    g = [[] for _ in range(numCourses)]
    indeg = [0] * numCourses
    for b, a in prerequisites:        # 修 b 前先修 a
        g[a].append(b); indeg[b] += 1
    q = deque(i for i in range(numCourses) if indeg[i] == 0)
    seen = 0
    while q:
        u = q.popleft(); seen += 1   # 修掉 u
        for v in g[u]:
            indeg[v] -= 1            # 后继入度减一
            if indeg[v] == 0: q.append(v)
    return seen == numCourses        # 修完=无环

Java

public boolean canFinish(int n, int[][] pre) {
    List<List<Integer>> g = new ArrayList<>();
    for (int i = 0; i < n; i++) g.add(new ArrayList<>());
    int[] indeg = new int[n];
    for (int[] p : pre) { g.get(p[1]).add(p[0]); indeg[p[0]]++; }
    Deque<Integer> q = new ArrayDeque<>();
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.offer(i);
    int seen = 0;
    while (!q.isEmpty()) {
        int u = q.poll(); seen++;        // 修掉 u
        for (int v : g.get(u))
            if (--indeg[v] == 0) q.offer(v); // 减到0入队
    }
    return seen == n;
}

C++

bool canFinish(int n, vector<vector<int>>& pre) {
    vector<vector<int>> g(n);
    vector<int> indeg(n, 0);
    for (auto& p : pre) { g[p[1]].push_back(p[0]); indeg[p[0]]++; }
    queue<int> q;
    for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);
    int seen = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop(); seen++;   // 修掉 u
        for (int v : g[u])
            if (--indeg[v] == 0) q.push(v);    // 减到0入队
    }
    return seen == n;
}