课程表 | 每日算法 · 变量语义法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a_i, b_i]，表示如果要学习课程 a_i 则必须先学习课程 b_i。请你判断是否可能完成所有课程的学习？

示例 1

输入：numCourses = 2, prerequisites = [[1,0]]

输出：true

先修关系：0 → 1，无环，可以学完。

示例 2

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]

输出：false

0 和 1 互相依赖，形成环，无法完成。

💭 模拟答题者思考

1. 我先想：能不能学完所有课，等价于先修关系有没有形成环。

2. 有环就永远卡在某个互相等待的圈子里，返回 false。

3. 拓扑排序的思路：每次选一门「没有未满足先修」的课来学，学完就解锁后续课程。

4. 用入度数组 + 队列（Kahn 算法）：indeg==0 的课先入队，弹出后给邻居 indeg--，新变 0 的再入队。

5. 最终 taken == numCourses 说明所有课都排进了合法顺序，无环。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`graph[u]`	list<int>[]	定义：先修图，边 b→a 表示学完 b 才能学 a 维护：建图后不变，graph[b] 存所有依赖 b 的课程更新：遍历 prerequisites 时 graph[b].append(a)
`indeg[v]`	int[]	定义：课程 v 还剩多少门先修课未满足维护：每门课被「学完」时，其邻居 indeg-- 更新：建边 b→a 时 indeg[a]++；从队列弹出 u 时对每个 v∈graph[u] 执行 indeg[v]--
`queue`	queue<int>	定义：当前所有先修已满足、可以立即选修的课程维护：弹出学完的课程，把新满足条件的课程入队更新：初始化时入队所有 indeg==0 的课；每轮 indeg[v] 变 0 时 v 入队
`taken`	int	定义：已成功选修的课程数维护：每从队列弹出一门课 taken++ 更新：taken == numCourses 则无环，否则有环

⌨️ 落码步骤

1. 建图：对每条 [a,b]，添加边 b→a，indeg[a]++

2. 将所有 indeg==0 的课程入队

3. 循环：弹出 u，taken++，对 graph[u] 中每个 v 执行 indeg[v]--，若变 0 则入队

4. 返回 taken == numCourses

💻 代码实现

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses

        for a, b in prerequisites:
            graph[b].append(a)  # 先学 b，再学 a
            indeg[a] += 1

        queue = [i for i in range(numCourses) if indeg[i] == 0]
        taken = 0

        while queue:
            u = queue.pop()
            taken += 1
            for v in graph[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    queue.append(v)

        return taken == numCourses

class Solution {
public:
    bool canFinish(int numCourses, vector>& prerequisites) {
        vector> graph(numCourses);
        vector indeg(numCourses, 0);

        for (auto& p : prerequisites) {
            int a = p[0], b = p[1];
            graph[b].push_back(a);
            indeg[a]++;
        }

        queue q;
        for (int i = 0; i < numCourses; i++)
            if (indeg[i] == 0) q.push(i);

        int taken = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            taken++;
            for (int v : graph[u]) {
                if (--indeg[v] == 0)
                    q.push(v);
            }
        }
        return taken == numCourses;
    }
};
// 时间 O(V+E)，空间 O(V+E)

📈 复杂度分析

时间复杂度 O(V + E)

空间复杂度 O(V + E)

⚠️ 常见坑

❗ 建边方向搞反：prerequisites[i]=[a,b] 表示 b 是 a 的先修，应建边 b→a，不是 a→b。

❗ 用 DFS 判环时状态要分三种（未访问/访问中/已完成），只分两种会漏判。

❗ 有环时 Kahn 算法 taken < numCourses，不能只检查队列是否为空就返回 true。

🔍 必测边界 Case

Case 1：无先修要求

numCourses = 3, prerequisites = [] → true

Case 2：自环

numCourses = 1, prerequisites = [[0,0]] → false

Case 3：长链无环

numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]] → true