LC207. 课程表

题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a(i), b(i)] ，表示如果要学习课程 a(i) 则 必须 先学习课程 b(i)。 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1： 输入：numCourses = 2, prerequisites = [[1,0]] 输出：true 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。 示例 2： 输入：numCourses = 2, prerequisites = [[1,0],[0,1]] 输出：false 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

题目解析

题目在说什么

想象一下，你是一个大学生，要选课。有些课有“先修课”要求，比如“学《机器学习》之前必须先学《线性代数》”。现在给你一个课程列表（0 到 numCourses-1）和一个先修关系列表，比如 [1,0] 表示“学1之前必须先学0”。你要判断：能不能把这些课全部学完？如果先修关系里出现了循环依赖，比如“学1要学0，学0要学1”，那就永远学不完，返回 false；否则返回 true。

思路是怎么来的

这个问题本质上是在问：这些课程之间的依赖关系有没有形成一个死循环？ 如果没有循环，就能按顺序学完；如果有循环，就永远卡住。

怎么判断有没有循环呢？我们可以用“拓扑排序”的思路。拓扑排序就像给课程排一个“学习顺序表”，保证学每门课的时候，它的先修课都已经学过了。如果排不出来（比如有循环依赖），就说明不可能。

怎么排？一个直观的想法是：先学那些没有先修课的课（入度为0的课），学完它们之后，那些依赖它们的课就少了一个先修要求。如果某门课的所有先修课都学完了，它就可以接着学。重复这个过程，直到所有课都学完，或者发现有些课永远无法学（因为它的先修课有循环依赖）。

这个思路很像“修水管”：先修课是上游，后续课是下游。如果上游的水（先修课）都流完了，下游才能开始流。如果某个下游永远等不到上游的水，就说明水管堵了（有环）。

代码逐步拆解

我们来看参考代码，一步步拆解。

1. 建图：把依赖关系存成“邻接表”

Map<Integer, List<Integer>> adjList = new HashMap<>();
int[] inDegree = new int[numCourses];

这里我们用了两个东西：

• adjList：一个“邻接表”，用来存每门课后面跟着哪些课。比如 adjList.get(b) 返回一个列表，里面是所有依赖 b 的课（即 b 是它们的先修课）。
• inDegree：一个数组，记录每门课有多少个先修课（即入度）。比如 inDegree[2] = 1 表示课程2有1个先修课。

为什么用这两个？因为我们要快速知道：某门课学完后，哪些课可以“解锁”了（入度减1）；以及哪些课已经可以学了（入度为0）。

for (int[] prerequisite : prerequisites) {
    int a = prerequisite[0];
    int b = prerequisite[1];
    adjList.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
    inDegree[a]++;
}

遍历每个先修关系 [a, b]（学 a 之前必须先学 b）：

• 在 adjList 中，给 b 的列表里加上 a，表示“b 是 a 的先修课”。
• 同时，a 的入度加1，表示 a 又多了一个先修课。

这样建完图后，我们就知道每门课依赖谁、谁依赖它。

2. 初始化队列：把“没有先修课”的课先加入队列

Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
    if (inDegree[i] == 0) {
        queue.offer(i);
    }
}

入度为0的课，就是那些没有先修课、可以直接学的课。我们把这些课先放进一个队列里，准备开始“学习”。

3. BFS 拓扑排序：依次“学”课，并更新依赖

while (!queue.isEmpty()) {
    int cur = queue.poll();
    if (adjList.containsKey(cur)) {
        for (int nxt : adjList.get(cur)) {
            inDegree[nxt]--;
            if (inDegree[nxt] == 0) {
                queue.offer(nxt);
            }
        }
    }
}

每次从队列里取出一门课 cur，表示“学完了这门课”。然后：

• 检查 cur 有没有后续课（即依赖它的课）。如果有，就遍历这些后续课 nxt。