LC207　课程表¶

中等通过率 57.4%python3核心代码模式图论样例通过牛客 AC深度优先搜索广度优先搜索图拓扑排序有向无环图

讲解章节：拓扑排序

一句话

先修关系构成有向图，能修完全部课程当且仅当这张图里没有环。

解题思路¶

这题考什么¶

「学 a 之前必须先学 b」是一条有向边 b -> a：b 在前，a 在后。一份可行的修课顺序就是这张图的一个拓扑序——每条边都从先修指向后修。有向图存在拓扑序的充要条件是它无环：环上的课互为前置，谁也排不到最前面。所以本题等价于「判断有向图是否有环」。

用 Kahn 算法（拓扑排序的入度剥离法）：

入度 = 一门课还有几门先修没学完。
入度为 0 的课现在就能学，进队；
每学完一门，把它指向的后继课入度各减 1，减到 0 的说明先修齐了，进队。

队列空掉时，出过队的课数就是能学完的课数。若它小于 numCourses，剩下的课全在环里（环上每个点的入度永远减不到 0）。

0 -> 1        入度: 0 号 0、1 号 1     可以修完
0 -> 1 -> 0   入度: 0 号 1、1 号 1     一开始就没有入度 0 的点 -> 有环

拓扑排序的完整讲法见拓扑排序。

数据规模与复杂度¶

1 <= numCourses <= 2000，先修对最多 5000 条，且互不相同。建图扫一遍边 O(E)，每个点进出队各一次、每条边被松弛一次，合计时间 O(V + E) = 2000 + 5000，空间 O(V + E) 存邻接表与入度表。朴素做法「每次找一门没有未修先修的课、修掉、重扫」是 O(V*E) = 1e7，虽然本题也能过，但入度表把「重扫」摊成了 O(1) 的减法，没有理由不用。

坑在哪¶

边的方向别接反。prerequisites[i] = [a, b] 的语义是「先 b 后 a」，所以邻接表要存 b -> a、给 a 的入度加一。存成 a -> b 时，示例 1 的 [[1,0]] 会算成「先 1 后 0」——这条链同样无环，答案照样是 true，样例根本测不出方向错；真正出问题的是不对称的数据，错得很隐蔽。
用 Kahn 算法而不是递归染色 DFS。numCourses 可到 2000，一条 2000 长的链会让递归深度到 2000，超过 CPython 默认的 1000 层上限，直接 RecursionError。
判定条件是「出队总数 == numCourses」，不是「队列曾经空过」。环外的点都能正常出队，只看队列空不空永远为真，必须数出队个数。
没有任何先修关系（prerequisites 为空）时所有课入度都是 0，初始化时要把全部入度为 0 的点一次性入队，漏掉这一步会一开始就空队返回 false。
自环 [a, a] 表示「学 a 之前要先学 a」，本身就是长度为 1 的环。入度法天然处理：a 的入度恒为 1，永远进不了队，出队数不足，返回 false。

样例复核¶

示例 2 的 [[1,0],[0,1]]：0 号入度 1（来自 1），1 号入度 1（来自 0），初始队列为空，出队数 0 < 2，返回 false，与样例一致。

参考实现¶

solutions/leetcode/LC207/sol.py
from collections import deque
from typing import List, Optional


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # nxt[b] 存「学完 b 之后才解锁的课」，indeg[a] 存 a 还欠几门先修
        nxt = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses
        for a, b in prerequisites:
            # [a, b] 读作「先 b 后 a」，所以边是 b -> a，方向接反会算出另一张图
            nxt[b].append(a)
            indeg[a] += 1

        # 起点是当前一门先修都不欠的课；没有先修关系时这里会把全部课一次装进队列
        q = deque(i for i in range(numCourses) if indeg[i] == 0)
        done = 0

        # 每出队一门课就当作已修完，随即把它解锁的后继课的欠账各减一门
        while q:
            cur = q.popleft()
            done += 1
            for to in nxt[cur]:
                indeg[to] -= 1
                # 减到 0 说明这门课的先修全部到齐，此刻才可入队
                if indeg[to] == 0:
                    q.append(to)

        # 环上每个点的入度永远减不到 0，出不了队；出队数不足即说明有环
        return done == numCourses

LC207 课程表¶