LeetCode LCR 113. 课程表 II

Categories:

题目描述
思路分析
1. 解法一：BFS 拓扑排序（Kahn 算法，推荐）
2. 解法二：DFS 拓扑排序
相似题目

题目描述

✅ LCR 113. 课程表 II

思路分析

解法一：BFS 拓扑排序（Kahn 算法，推荐）

核心思路：

拓扑排序本质是：每次选出入度为 0 的节点（没有前置依赖的课），将其加入结果，同时将其后继节点的入度减一。

使用入度数组 inDegree[] 记录每门课的前置依赖数量，邻接表 adj[] 记录每门课解锁的后继课程。

将所有入度为 0 的课程入队，BFS 逐层处理：出队一门课 → 加入结果 → 将其邻居入度减一 → 若邻居入度变为 0 则入队。

若最终结果数组长度等于 numCourses，说明无环，返回结果；否则存在环，返回空数组。

复杂度分析：

时间复杂度：O(V + E)，其中 V 为课程数，E 为先修关系数

空间复杂度：O(V + E)，用于存储邻接表和入度数组

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 构建邻接表和入度数组
        List<List<Integer>> adj = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] pre : prerequisites) {
            // pre[1] -> pre[0]，学 pre[0] 前必须先学 pre[1]
            adj.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }

        // 将所有入度为 0 的课程加入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int[] order = new int[numCourses];
        int idx = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            // 当前课程无前置依赖，可以学习
            order[idx++] = course;
            for (int next : adj.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 {
    // 构建邻接表和入度数组
    adj := make([][]int, numCourses)
    inDegree := make([]int, numCourses)
    for i := range adj {
        adj[i] = []int{}
    }
    for _, pre := range prerequisites {
        // pre[1] -> pre[0]，学 pre[0] 前必须先学 pre[1]
        adj[pre[1]] = append(adj[pre[1]], pre[0])
        inDegree[pre[0]]++
    }

    // 将所有入度为 0 的课程加入队列
    queue := []int{}
    for i := 0; i < numCourses; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    order := make([]int, 0, numCourses)
    for len(queue) > 0 {
        course := queue[0]
        queue = queue[1:]
        // 当前课程无前置依赖，可以学习
        order = append(order, course)
        for _, next := range adj[course] {
            inDegree[next]--
            // 前置依赖全部完成，可以学习
            if inDegree[next] == 0 {
                queue = append(queue, next)
            }
        }
    }

    // 若所有课程均已排入，则返回顺序；否则存在环
    if len(order) == numCourses {
        return order
    }
    return []int{}
}

解法二：DFS 拓扑排序

核心思路：

使用 DFS 对有向图进行后序遍历，后序遍历的逆序即为拓扑排序结果。

用 state[] 数组记录每个节点的访问状态：0 = 未访问，1 = 访问中（在当前 DFS 路径上），2 = 已完成。

若 DFS 过程中遇到状态为 1 的节点，说明存在环，返回 false。

每个节点完成 DFS 后将其压栈，最终将栈逆序即为拓扑排序。

复杂度分析：

时间复杂度：O(V + E)，其中 V 为课程数，E 为先修关系数

空间复杂度：O(V + E)，用于存储邻接表和递归调用栈

class Solution {
    private List<List<Integer>> adj;
    // 0: 未访问，1: 访问中，2: 已完成
    private int[] state;
    private int[] order;
    private int idx;
    private boolean hasCycle;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        adj = new ArrayList<>();
        state = new int[numCourses];
        order = new int[numCourses];
        idx = numCourses - 1;
        hasCycle = false;

        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
        }

        // 对每个未访问的节点进行 DFS
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0) {
                dfs(i);
            }
        }

        return hasCycle ? new int[0] : order;
    }

    private void dfs(int course) {
        if (hasCycle) {
            return;
        }
        // 标记为访问中
        state[course] = 1;
        for (int next : adj.get(course)) {
            if (state[next] == 0) {
                dfs(next);
            } else if (state[next] == 1) {
                // 遇到访问中的节点，说明存在环
                hasCycle = true;
                return;
            }
        }
        // 后序：DFS 完成后加入结果（逆序填充即为拓扑序）
        state[course] = 2;
        order[idx--] = course;
    }
}

func findOrder(numCourses int, prerequisites [][]int) []int {
    adj := make([][]int, numCourses)
    // 0: 未访问，1: 访问中，2: 已完成
    state := make([]int, numCourses)
    order := make([]int, numCourses)
    idx := numCourses - 1
    hasCycle := false

    for i := range adj {
        adj[i] = []int{}
    }
    for _, pre := range prerequisites {
        adj[pre[1]] = append(adj[pre[1]], pre[0])
    }

    var dfs func(course int)
    dfs = func(course int) {
        if hasCycle {
            return
        }
        // 标记为访问中
        state[course] = 1
        for _, next := range adj[course] {
            if state[next] == 0 {
                dfs(next)
            } else if state[next] == 1 {
                // 遇到访问中的节点，说明存在环
                hasCycle = true
                return
            }
        }
        // 后序：DFS 完成后加入结果（逆序填充即为拓扑序）
        state[course] = 2
        order[idx] = course
        idx--
    }

    // 对每个未访问的节点进行 DFS
    for i := 0; i < numCourses; i++ {
        if state[i] == 0 {
            dfs(i)
        }
    }

    if hasCycle {
        return []int{}
    }
    return order
}

相似题目

题目	难度	考察点
207. 课程表	中等	拓扑排序、环检测
269. 火星词典	困难	拓扑排序、图
310. 最小高度树	中等	拓扑排序、图
444. 序列重建	中等	拓扑排序
802. 找到最终的安全状态	中等	DFS、拓扑排序
1136. 并行课程	中等	拓扑排序、BFS
2115. 从给定原材料中找到所有可以做出的菜	中等	拓扑排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/29135590