课程表 II 图解题解

这道题到底在问什么

课程数

4 门（0,1,2,3）

先修

学 1、2 前先学 0；学 3 前先学 1 和 2

输出

[0, 1, 2, 3]

最优解：一步一步想明白

1. 3最朴素的做法：每轮扫一遍所有课，挑还没学、且前置都学完的去学。可每轮都要把每门课的前置重新检查一次，n 门课最坏扫 n 轮——大量重复。
2. 4转折：与其每轮重数，不如给每门课维护入度（指向它的箭头数 = 还差几门前置）。入度 0 的先入队；每次出队一门课就追加进 order，再把它解锁的课入度各减 1，谁减到 0 才入队。这样每条边只用一次，order 收集的顺序就是拓扑序。
3. 5indeg = [0,1,1,2]邻接表 g[0]=[1,2]、g[1]=[3]、g[2]=[3]，数出入度：课 0 没前置(0)，课 1、2 各等一门(1)，课 3 等两门(2)。order 现在还空。
4. 6q = [0]把入度为 0 的课入队：只有课 0 没前置，先放进队列，作为「现在就能学」的起点。
5. 7order = [0]取出 0 学完，第一时间把它追加进 order=[0]——出队顺序就是答案顺序。接着看它解锁了哪些课：g[0]=[1,2]。
6. 8indeg[1]: 1 → 0 ✓沿边 0→1，课 1 入度 1→0：它唯一的前置 0 学完了，立刻入队。
7. 9indeg[2]: 1 → 0 ✓再沿边 0→2，课 2 入度也减到 0，入队。现在队列 [1,2] 都待学，0 处理完变绿。 队列里 1、2 谁先弹取决于入队次序，所以 [0,2,1,3] 等也是合法拓扑序——顺序和我不同不代表错。
8. 10order = [0,1]取出 1 学完，追加进 order=[0,1]。它解锁课 3：g[1]=[3]。
9. 11indeg[3]: 2 → 1沿边 1→3，课 3 入度 2→1：还没到 0（还差课 2）——所以课 3 暂不入队。关键：减入度 ≠ 立即入队，只有归零才入队。
10. 12order = [0,1,2]取出 2 学完，追加进 order=[0,1,2]。它也解锁课 3：g[2]=[3]。
11. 13indeg[3]: 1 → 0 ✓沿边 2→3，课 3 入度 1→0：两门前置都学完了，入队。对比上一步——同样是减入度，这次归零所以入队。
12. 14order = [0,1,2,3]，len==n取出 3 学完，order=[0,1,2,3]。长度 4 = 课程数 n，返回这个顺序 [0,1,2,3]。若图有环，环上的课入度永远减不到 0、进不了队，order 长度小于 n，就返回空数组。 反过来：若图里有环，环上的课入度永远减不到 0、进不了队，order 长度 ＜ n，就返回 [] 表示无法完成。
13. 17凡是「给一堆依赖关系排出可行执行顺序」都是拓扑排序：课程安排、任务调度、编译依赖、Excel 公式求值。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def findOrder(self, numCourses, prerequisites):
        graph = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses
        for a, b in prerequisites:        # 学 a 前要先学 b
            graph[b].append(a)
            indeg[a] += 1
        q = [i for i in range(numCourses) if indeg[i] == 0]  # 入度0先学
        order = []; head = 0
        while head < len(q):
            cur = q[head]; head += 1
            order.append(cur)
            for nxt in graph[cur]:
                indeg[nxt] -= 1
                if indeg[nxt] == 0: q.append(nxt)
        return order if len(order) == numCourses else []  # 有环则空

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indeg(numCourses, 0);
        for (auto& p : prerequisites) { graph[p[1]].push_back(p[0]); indeg[p[0]]++; }
        queue<int> q;
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.push(i);
        vector<int> order;
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            order.push_back(cur);
            for (int nxt : graph[cur]) if (--indeg[nxt] == 0) q.push(nxt);
        }
        return order.size() == numCourses ? order : vector<int>{};   // 有环则空
    }
};

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        int[] indeg = new int[numCourses];
        for (int[] p : prerequisites) { graph.get(p[1]).add(p[0]); indeg[p[0]]++; }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
        int[] order = new int[numCourses]; int idx = 0;
        while (!q.isEmpty()) {
            int cur = q.poll(); order[idx++] = cur;
            for (int nxt : graph.get(cur)) if (--indeg[nxt] == 0) q.offer(nxt);
        }
        return idx == numCourses ? order : new int[0];   // 有环则空
    }
}

# 「有依赖、排一个可行顺序」都套
q = deque(入度0的点); order = []
while q:
    u = q.popleft(); order.append(u)   # 收集顺序
    for v in g[u]:
        indeg[v] -= 1
        if indeg[v]==0: q.append(v)
return order if len(order)==n else []   # 不全=有环

复杂度

面试官可能追问