LeetCode LCR 113. 课程表 II

约 5 分钟
文章信息 5 个分类 5 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
深度优先搜索 广度优先搜索 LCR 图 拓扑排序

题目描述

✅ LCR 113. 课程表 II

image-20260929004643813

image-20260929004643814

题意分析

prerequisites 中的 [a, b] 表示学习 a 前必须先完成 b。返回包含全部课程的一种合法学习顺序，答案不唯一；若依赖关系使部分课程无法完成，则返回空数组。

解法：入度归零的拓扑排序

核心思路

[!blue]

将先修关系建成有向边 b -> a，邻接表保存每门课完成后能影响哪些后续课程。indegree[x] 表示课程 x 还有多少条先修关系未解除；它为 0 时，这门课才可以学习。

先将所有零入度课程入队，包括没有依赖的孤立课程。每次取出一门课写入 order，再沿其出边将后继入度减一；只有刚好减到 0 的后继才入队。这使已写入结果的每门课，其先修课都排在它前面，也避免每轮重新检查全部课程。

若队列为空时仍有课程没输出，这些剩余节点都还有来自剩余节点的入边。不断沿未完成的先修关系向前追溯，在有限节点中必然遇到重复节点，因此剩余图中存在环。未输出的课程可能位于环中，也可能依赖这个环，都不能纳入完整学习顺序。

所以输出数量等于 numCourses 时，order 就是合法答案；数量不足时返回空数组。多个零入度课程可以任选一个先处理，本题不要求唯一顺序或最小字典序。

解题步骤

  1. 为每门课程建立邻接表；每条 [a, b] 加入边 b -> a，并增加 a 的入度。
  2. 扫描全部课程，将入度为 0 的课程加入队列。
  3. 取出队首课程，追加到结果中。
  4. 将它的每个后继入度减一，减到 0 时入队。
  5. 队列耗尽后检查结果长度：包含全部课程则返回结果，否则返回空数组。

代码实现

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[] indegree = new int[numCourses];

        for (int[] edge : prerequisites) {
            graph.get(edge[1]).add(edge[0]);
            indegree[edge[0]]++;
        }

        Queue<Integer> queue = new ArrayDeque<>();

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

        int[] order = new int[numCourses];
        int idx = 0;

        while (!queue.isEmpty()) {
            int course = queue.poll();

            order[idx++] = course;

            // 学完当前课程后，释放所有依赖它的后续课程。
            for (int next : graph.get(course)) {
                indegree[next]--;

                if (indegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        return idx == numCourses ? order : new int[0];
    }
}

func findOrder(numCourses int, prerequisites [][]int) []int {
    graph := make([][]int, numCourses)
    indegree := make([]int, numCourses)
    for _, edge := range prerequisites {
        course := edge[0]
        pre := edge[1]
        graph[pre] = append(graph[pre], course)
        indegree[course]++
    }

    queue := make([]int, 0)
    for course := 0; course < numCourses; course++ {
        if indegree[course] == 0 {
            queue = append(queue, course)
        }
    }

    order := make([]int, 0, numCourses)
    for head := 0; head < len(queue); head++ {
        course := queue[head]
        order = append(order, course)
        // 入度降为 0 时，说明该课程的先修课已经全部完成。
        for _, next := range graph[course] {
            indegree[next]--
            if indegree[next] == 0 {
                queue = append(queue, next)
            }
        }
    }
    if len(order) != numCourses {
        return []int{}
    }
    return order
}

复杂度分析

  • 时间复杂度：$O(n+m)$，n 为课程数，m 为先修关系数。每门课至多入队、出队一次，每条边只在起点出队时处理一次。
  • 空间复杂度：$O(n+m)$，邻接表保存全部边，入度数组、队列和结果各占 $O(n)$。

关键点总结

[!green]

  • 边从先修课指向后续课，入度反映尚未满足的依赖。
  • 初始加入全部零入度课程，才能覆盖所有互不相连的部分。
  • 出队时记录学习顺序，最后用输出数量判断是否存在无法完成的课程。
  • 队列中同时存在多个选择不代表无解，任意选择都能继续得到合法拓扑顺序。

易错点总结

[!yellow]

  • 先修课指向后续课，入度表示仍未完成的先修数量。
  • 所有入度 0 的课程都先入队，后继只在减到 0 时加入。
  • 输出数量不足课程总数就返回空数组，任意合法拓扑顺序都可接受。

相似题目

题目 难度 关联与区别
207. 课程表 中等 依赖图相同，原题只判断能否完成，本题还需输出一个合法拓扑顺序。
802. 找到最终的安全状态 中等 同样可用度数逐步剥离节点，原题在反图中从终点消除安全节点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/29135590
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！