题目

思路

一句话：把「能否修完」转化为「依赖有向图里有没有环」，再用拓扑排序检验。

先想最直白的做法：枚举所有可能的选课顺序，逐个检查是否满足每一条先修关系。课程最多 2000 门，排列数量是阶乘级，完全不可行。

退一步，用 DFS 沿着先修链往下走似乎可行；但如果只用一个「访问过」的 set，分不清「正在当前路径上」和「早已验证完成」，很容易把无环图误判成有环。

关键观察：一张依赖图没有环时，总能把所有点排成一个线性的先后顺序，这个顺序叫拓扑序。所以问题退化成：能不能把 numCourses 个点全部排进拓扑序。全排进去就是无环；排不完整，剩下的点必然构成环。

求拓扑序有两种常用姿势：

• Kahn 算法（BFS）：不停修掉「当前没有任何未修先修课」的课程，直观、好写、不依赖递归。本文选这个。
• DFS 三色标记：0 未访问、1 正在当前路径里、2 已完成；DFS 时再遇到 1，就是遇到了环。

选定 Kahn 后，把 [a, b] 画成边 b → a，并统计每门课的入度：还有几个先修没完成。入度为 0 的课现在就可以直接修。

解法

维护一张邻接表和一个入度数组，用队列不断处理入度为 0 的课：

1. 初始化 graph 与 indegree；对每条 [a, b] 加边 graph[b].push_back(a)，同时 indegree[a] += 1。
2. 把当前所有 indegree == 0 的课入队。
3. 每从队头取出一门课，就代表它已修完，done++；再遍历它的后继课，把后继入度减 1。
4. 若某个后继入度减到 0，说明它的先修都已修完，把它也入队。
5. 循环结束后，若 done == numCourses 返回 true；否则剩下没被处理的课形成环，返回 false。

以自造示例 1 走一遍（边：[1,0] → 0→1、[2,1] → 1→2、[3,2] → 2→3）：