课程表 II 图解题解

这道题到底在问什么

输入

numCourses = 6 prerequisites = [[1,0],[2,0],[3,1],[3,2],[4,3],[5,4]]

输出

[0,1,2,3,4,5]

最优解：一步一步想明白

1. 3记住这一句：入度0 = 现在就能学；学完一门就给后续课「松绑」。下面一步步建图再排序。
2. 4先把 6 门课 0~5 摆成 6 个节点，入度（还有几门没学的先修课）都标 0。接下来逐条读先修关系，连出有向边。
3. 5读到 [1, 0]：想学课 1，必须先学课 0。高亮这两门课——课 0 要排在课 1 前面。
4. 6连一条有向边 0→1（先学 0 才能学 1）。课 1 又多了一门没学的先修课，入度 +1（看它上方）。
5. 7读到 [2, 0]：想学课 2，必须先学课 0。高亮这两门课——课 0 要排在课 2 前面。
6. 8连一条有向边 0→2（先学 0 才能学 2）。课 2 又多了一门没学的先修课，入度 +1（看它上方）。
7. 9读到 [3, 1]：想学课 3，必须先学课 1。高亮这两门课——课 1 要排在课 3 前面。
8. 10连一条有向边 1→3（先学 1 才能学 3）。课 3 又多了一门没学的先修课，入度 +1（看它上方）。
9. 11读到 [3, 2]：想学课 3，必须先学课 2。高亮这两门课——课 2 要排在课 3 前面。
10. 12连一条有向边 2→3（先学 2 才能学 3）。课 3 又多了一门没学的先修课，入度 +1（看它上方）。
11. 13读到 [4, 3]：想学课 4，必须先学课 3。高亮这两门课——课 3 要排在课 4 前面。
12. 14连一条有向边 3→4（先学 3 才能学 4）。课 4 又多了一门没学的先修课，入度 +1（看它上方）。
13. 15读到 [5, 4]：想学课 5，必须先学课 4。高亮这两门课——课 4 要排在课 5 前面。
14. 16连一条有向边 4→5（先学 4 才能学 5）。课 5 又多了一门没学的先修课，入度 +1（看它上方）。
15. 17建图完成。开始 Kahn 拓扑排序：看节点上方入度，课 0 入度为 0（没有任何先修课要先学）→ 入队，现在就能学。
16. 18队首课 0 出队，现在去学它，追加到学习顺序：[0]。学完后给它解锁的后续课松绑。
17. 19学完课 0 后，它解锁的后续课 1 少了一门待学先修课：入度减 1，变为 0——降到 0，马上可以学。
18. 20课 1 的入度降到 0（先修课都学完了）→ 入队，等待安排。
19. 21学完课 0 后，它解锁的后续课 2 少了一门待学先修课：入度减 1，变为 0——降到 0，马上可以学。
20. 22课 2 的入度降到 0（先修课都学完了）→ 入队，等待安排。
21. 23队首课 1 出队，现在去学它，追加到学习顺序：[0,1]。学完后给它解锁的后续课松绑。
22. 24学完课 1 后，它解锁的后续课 3 少了一门待学先修课：入度减 1，变为 1，还有别的先修课没学完，暂不入队。
23. 25队首课 2 出队，现在去学它，追加到学习顺序：[0,1,2]。学完后给它解锁的后续课松绑。
24. 26学完课 2 后，它解锁的后续课 3 少了一门待学先修课：入度减 1，变为 0——降到 0，马上可以学。
25. 27课 3 的入度降到 0（先修课都学完了）→ 入队，等待安排。
26. 28队首课 3 出队，现在去学它，追加到学习顺序：[0,1,2,3]。学完后给它解锁的后续课松绑。
27. 29学完课 3 后，它解锁的后续课 4 少了一门待学先修课：入度减 1，变为 0——降到 0，马上可以学。
28. 30课 4 的入度降到 0（先修课都学完了）→ 入队，等待安排。
29. 31队首课 4 出队，现在去学它，追加到学习顺序：[0,1,2,3,4]。学完后给它解锁的后续课松绑。
30. 32学完课 4 后，它解锁的后续课 5 少了一门待学先修课：入度减 1，变为 0——降到 0，马上可以学。
31. 33课 5 的入度降到 0（先修课都学完了）→ 入队，等待安排。
32. 34学课 5，加入学习顺序。所有 6 门课都已出队、入度全清零——拓扑排序完成！出队顺序 [0,1,2,3,4,5] 就是一个合法学习顺序，即答案。

⚠️ 容易写错的地方

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

def findOrder(numCourses, prerequisites):
    g = [[] for _ in range(numCourses)]
    indeg = [0] * numCourses
    for a, b in prerequisites:   # 先学 b 才能学 a
        g[b].append(a)
        indeg[a] += 1
    q = deque([c for c in range(numCourses) if indeg[c] == 0])
    order = []
    while q:
        c = q.popleft(); order.append(c)
        for nb in g[c]:
            indeg[nb] -= 1
            if indeg[nb] == 0: q.append(nb)
    return order if len(order) == numCourses else []

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites){
    vector<vector<int>> g(numCourses);
    vector<int> indeg(numCourses, 0);
    for(auto& p : prerequisites){   // p=[a,b] 先学 b 才能学 a
        g[p[1]].push_back(p[0]);
        indeg[p[0]]++;
    }
    queue<int> q;
    for(int c=0;c<numCourses;++c) if(indeg[c]==0) q.push(c);
    vector<int> order;
    while(!q.empty()){
        int c=q.front(); q.pop(); order.push_back(c);
        for(int nb : g[c]) if(--indeg[nb]==0) q.push(nb);
    }
    return order.size()==(size_t)numCourses ? order : vector<int>{};
}

public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<List<Integer>> g = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) g.add(new ArrayList<>());
    int[] indeg = new int[numCourses];
    for (int[] p : prerequisites) {   // p=[a,b] 先学 b 才能学 a
        g.get(p[1]).add(p[0]);
        indeg[p[0]]++;
    }
    Queue<Integer> q = new LinkedList<>();
    for (int c = 0; c < numCourses; c++) if (indeg[c] == 0) q.offer(c);
    int[] order = new int[numCourses];
    int idx = 0;
    while (!q.isEmpty()) {
        int c = q.poll(); order[idx++] = c;
        for (int nb : g.get(c)) {
            if (--indeg[nb] == 0) q.offer(nb);
        }
    }
    return idx == numCourses ? order : new int[0];
}

复杂度

面试官可能追问