207. 课程表

题目链接（中等）

题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a_i, b_i]，表示如果要学习课程 a_i 则必须先学习课程 b_i。

例如，先修课程对 [0, 1] 表示：想要学习课程 0，你需要先完成课程 1。

请你判断是否可能完成所有课程的学习？如果可以，返回 true；否则，返回 false。

数据范围：

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
prerequisites[i] 中的所有课程对 互不相同

示例

示例 1：

输入： numCourses = 2, prerequisites = [[1,0]]
输出： true
解释： 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。这是可能的。

示例 2：

输入： numCourses = 2, prerequisites = [[1,0],[0,1]]
输出： false
解释： 学习课程 1 之前需要先完成课程 0，学习课程 0 之前需要先完成课程 1，不可能完成。

核心思路

把课程看成一个有向图的节点：

每门课是一个节点；
若学 a 前必须先学 b，则从 b 到 a 连一条有向边；
学习顺序就是一个拓扑排序。

结论：

如果图中有环，说明存在循环依赖，无法完成所有课程 → 返回 false；
如果图是有向无环图（DAG），存在拓扑排序 → 返回 true。

所以本题等价于判断有向图是否有环。

两种经典做法：

DFS：从每个节点出发，搜索过程中判断是否遇到「搜索中」的节点（说明有环）；
BFS（拓扑排序）：统计每个节点的入度，从入度为 0 的节点开始逐层剥离，看能否剥完所有节点。

方法一：DFS 判断环（三色标记）

思路及解法

用三种状态标记每个节点：

0：未搜索，还没访问过；
1：搜索中，正在 DFS 的递归栈里；
2：已完成，DFS 已回溯。

DFS 过程中，对当前节点 u 标记为 1，遍历它的所有邻居 v：

若 v == 0（未搜索），递归搜索 v；
若 v == 1（搜索中），说明从 v 出发绕回了自己，存在环，标记 valid = False；
若 v == 2（已完成），跳过（该分支已经处理过）。

当 u 的所有邻居都处理完后，把 u 标记为 2，并把 u 推入栈（本题只需要判断有环，所以栈可以省略）。

关键点：只有 v 处于「搜索中」时才意味着有环。这说明 v 在当前 DFS 路径上，从 u 又能走回 v，形成环。

代码

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        state = [0] * numCourses  # 0 未访问，1 访问中，2 已完成
        result = []

        for a, b in prerequisites:
            graph[b].append(a)  # b -> a

        def dfs(u: int) -> bool:
            state[u] = 1
            for v in graph[u]:
                if state[v] == 1:
                    return False
                if state[v] == 0 and not dfs(v):
                    return False
            state[u] = 2
            result.append(u)
            return True

        for i in range(numCourses):
            if state[i] == 0 and not dfs(i):
                return False
                
        return True

复杂度分析

时间复杂度：$O(n + m)$，$n$ 为课程数，$m$ 为先修课程数。每个节点和每条边各访问一次。
空间复杂度：$O(n + m)$，邻接表占 $O(n + m)$，递归栈深度最坏为 $O(n)$。

方法二：BFS 拓扑排序（入度法）

思路及解法

拓扑排序的直观流程：

统计每个节点的入度（有多少门课指向它，即它有多少先修课）；
把所有入度为 0 的节点（没有先修课的课）加入队列；
每次从队列取出一个节点 u，把它「学完」，并将 u 指向的所有节点 v 的入度减 1；
如果 v 的入度变为 0，说明它的先修课都学完了，把 v 加入队列；
统计一共处理了多少个节点。若等于 n，说明可以完成全部课程；否则存在环。

为什么有环就无法处理完？

环上的每个节点入度至少为 1（环上一个节点指向它），永远进不了队列，因此 visited 无法达到 n。

核心直觉：拓扑排序就是不断「剥掉没有先修课的课」，看能不能把整张图剥空。

代码

from collections import defaultdict, deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        edges = defaultdict(list)
        indeg = [0] * numCourses

        for a, b in prerequisites:
            edges[b].append(a)               # b → a
            indeg[a] += 1                    # a 的入度 +1

        # 所有入度为 0 的节点入队
        q = deque([u for u in range(numCourses) if indeg[u] == 0])
        visited = 0

        while q:
            u = q.popleft()
            visited += 1
            for v in edges[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)

        return visited == numCourses

复杂度分析

时间复杂度：$O(n + m)$，每个节点入队出队一次，每条边被处理一次。
空间复杂度：$O(n + m)$，邻接表 $O(n + m)$，队列最多 $O(n)$。

两种方法对比

方法	时间	空间	特点
DFS 三色标记	$O(n + m)$	$O(n + m)$	思路直观，判断环明显
BFS 拓扑排序	$O(n + m)$	$O(n + m)$	更符合「学习顺序」的直觉，可扩展为求拓扑序

关键细节

1. 边的方向

prerequisites[i] = [a, b] 表示「学 a 之前先学 b」，所以边的方向是：

$b \to a$

即 edges[b].append(a)，同时 a 的入度 +1。

搞反方向的话，统计入度和删边的逻辑都会错。

2. DFS 三色标记的含义

状态	含义	遇到时
`0`	未搜索	递归搜索
`1`	搜索中（在当前递归栈里）	发现环，标记 `valid = False`
`2`	已完成	跳过

为什么「搜索中」代表有环？

因为 visited[v] == 1 说明 v 是当前 DFS 路径上的祖先，从 u 又能回到 v，形成环。

为什么「已完成」不算有环？

因为 v 已经处理完了，它的所有出边都走过了，从 u 到 v 并不会回到 u。

3. BFS 中 `visited` 的作用

visited 统计的是已经「剥掉」的节点数。如果图是 DAG，最终 visited == n；如果有环，环上的节点入度永远大于 0，进不了队列，visited < n。

4. DFS 中为什么只在外层循环判断 `valid`

for i in range(numCourses):
    if valid and visited[i] == 0:
        dfs(i)

如果某个 DFS 已经发现了环（valid = False），就不用再搜索其他未访问的节点了，直接跳过。

总结

本质：把课程依赖关系建成有向图，判断图是否有环；
DFS 三色标记：0 未访问、1 搜索中（有环）、2 已完成；
BFS 拓扑排序：入度为 0 入队，剥离出边，减邻居入度，看能否剥完所有节点；
两种方法时间都是 $O(n + m)$；
通用套路：
- 有向图判断环 → 拓扑排序；
- 无向图判断环 → 并查集 / DFS。

207. 课程表

207. 课程表

题目描述

示例

核心思路

方法一：DFS 判断环（三色标记）

思路及解法

代码

复杂度分析

方法二：BFS 拓扑排序（入度法）

思路及解法

代码

复杂度分析

两种方法对比

关键细节

1. 边的方向

2. DFS 三色标记的含义

3. BFS 中 visited 的作用

4. DFS 中为什么只在外层循环判断 valid

总结

相关题目

3. BFS 中 `visited` 的作用

4. DFS 中为什么只在外层循环判断 `valid`