课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。
在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi]，表示如果要学习课程 ai，则必须先学习课程 bi。
例如，先修课程对 [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 。这是不可能的。
提示：
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[i]中的所有课程对互不相同
解法一（拓扑排序 BFS）：
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
vector<int> indegree(numCourses, 0);
for (auto& p : prerequisites)
{
int a = p[0];
int b = p[1];
adj[b].push_back(a);
indegree[a]++;
}
queue<int> q;
for (int i = 0; i < numCourses; ++i)
{
if (indegree[i] == 0)
{
q.push(i);
}
}
int visited = 0;
while (!q.empty())
{
int cur = q.front();
q.pop();
visited++;
for (int next : adj[cur])
{
indegree[next]--;
if (indegree[next] == 0)
{
q.push(next);
}
}
}
return visited == numCourses;
}
};
解法二（DFS 三色标记）：
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
for (auto& p : prerequisites)
{
adj[p[1]].push_back(p[0]);
}
vector<int> state(numCourses, 0);
for (int i = 0; i < numCourses; ++i)
{
if (state[i] == 0 && hasCycle(i, adj, state))
{
return false;
}
}
return true;
}
private:
bool hasCycle(int cur, vector<vector<int>>& adj, vector<int>& state)
{
state[cur] = 1;
for (int next : adj[cur])
{
if (state[next] == 1)
{
return true;
}
if (state[next] == 0 && hasCycle(next, adj, state))
{
return true;
}
}
state[cur] = 2;
return false;
}
};
核心思想
课程之间存在「先修」关系，天然可以用有向图来建模。
把每门课程看成一个节点，把先修关系看成一条有向边：
如果学课程
a之前必须先学b，就有一条从b指向a的边b -> a。
那么「能否完成所有课程」这个问题，就转化成了：
这张有向图中是否存在环？
如果存在环，例如 A -> B -> A，说明学 A 要先学 B，学 B 又要先学 A，互相卡死，永远无法开始，也就无法完成所有课程。
如果不存在环（也就是有向无环图 DAG），那么一定存在一个合法的学习顺序，可以按拓扑序依次修完所有课程。
所以这题本质上就是「有向图判环」，有两种经典做法：拓扑排序（BFS）和三色标记（DFS）。
把问题建模成有向图
先明确边的方向。
题目中 prerequisites[i] = [ai, bi] 表示学 ai 要先学 bi。
也就是「先修课 bi」指向「依赖它的课 ai」，方向是：
bi -> ai
对应到代码里：
adj[b].push_back(a);
indegree[a]++;
indegree[a] 表示课程 a 还有多少门先修课没有学。
入度为 0 的课程表示它没有任何先修课，可以直接学。
解法一：拓扑排序（BFS）
拓扑排序（Kahn 算法）的思路是「从没有先修课的课程开始，一门一门地学」。
1. 统计入度并建图
vector<vector<int>> adj(numCourses);
vector<int> indegree(numCourses, 0);
for (auto& p : prerequisites)
{
int a = p[0];
int b = p[1];
adj[b].push_back(a);
indegree[a]++;
}
2. 把所有入度为 0 的课程加入队列
queue<int> q;
for (int i = 0; i < numCourses; ++i)
{
if (indegree[i] == 0)
{
q.push(i);
}
}
这些课程不需要任何先修课，是「当前可以学」的课程。
3. 依次学习并更新后续课程的入度
int visited = 0;
while (!q.empty())
{
int cur = q.front();
q.pop();
visited++;
for (int next : adj[cur])
{
indegree[next]--;
if (indegree[next] == 0)
{
q.push(next);
}
}
}
每学完一门课程 cur，就把它指向的那些课程 next 的入度减 1。
当某门课程的入度降到 0 时，说明它的先修课都学完了，可以加入队列继续学。
4. 判断是否学完了所有课程
return visited == numCourses;
如果最终学完的课程数等于课程总数，说明不存在环，返回 true。
否则说明有一部分课程因为成环、入度永远不为 0，无法被学，返回 false。
解法二：DFS 三色标记
三色标记用三种状态标记每个节点：
0：未访问1：正在访问（当前 DFS 路径上）2：已访问完成（所有后继都处理完了）
vector<int> state(numCourses, 0);
从每个未访问的节点出发做 DFS：
for (int i = 0; i < numCourses; ++i)
{
if (state[i] == 0 && hasCycle(i, adj, state))
{
return false;
}
}
在 DFS 过程中：
bool hasCycle(int cur, vector<vector<int>>& adj, vector<int>& state)
{
state[cur] = 1;
for (int next : adj[cur])
{
if (state[next] == 1)
{
return true;
}
if (state[next] == 0 && hasCycle(next, adj, state))
{
return true;
}
}
state[cur] = 2;
return false;
}
关键判断是：在遍历 next 时，如果发现 next 的状态是 1（正在访问），说明从 next 出发又能走回当前路径上的节点，形成了一条回路，也就是有环。
如果 next 是 2（已访问完成），说明它已经被确认无环，直接跳过即可，避免重复遍历。
边界情况
如果没有先修课程，即 prerequisites 为空：
- 所有课程入度都是
0，拓扑排序能学完所有课程，返回true - DFS 中每个节点都无后继，不会发现环，返回
true
如果只有一门课程，无论有没有先修约束，只要不存在自环就能完成。
如果课程对里出现自环，例如 [0, 0]：
- 建图后节点
0有一条指向自己的边，入度恒为1，拓扑排序无法学完，返回false - DFS 中会走到状态为
1的自己，判定有环，返回false
正确性证明
我们证明：算法返回 true 当且仅当可以完成所有课程。
结论 1：能完成所有课程，当且仅当图中不存在环
如果图中存在环，环上每一门课程都依赖环上的另一门课程，没有哪门课能先开始，所以无法完成所有课程。
如果图中不存在环，也就是有向无环图，那么它一定存在至少一个入度为 0 的节点，可以按拓扑序依次修完所有课程。
因此「能否完成所有课程」等价于「图中是否有环」。
结论 2：拓扑排序能正确判断是否有环
拓扑排序每次取出入度为 0 的节点，并把它的出边指向的节点入度减 1。
如果图是 DAG，每轮都能取出至少一个入度为 0 的节点，最终所有节点都会被访问，visited == numCourses。
如果图中存在环，环上的节点入度永远大于 0，永远进不了队列，最终 visited < numCourses。
因此通过比较 visited 和 numCourses 就能正确判断是否有环。
结论 3：三色标记能正确检测环
DFS 中，节点状态变化为 0 -> 1 -> 2。
当遍历到状态为 1 的节点时，说明这条边指向了当前 DFS 递归栈上的某个祖先节点，必然形成环。
状态为 2 的节点已经被证明无环，不会误判。
因此三色标记能正确检测环。
得出结论
由结论 1 可知问题等价于判环。
由结论 2 和结论 3 可知，两种解法都能正确判环。
因此两个解法都能正确回答是否能完成所有课程。
举例理解
示例 1
以：
numCourses = 2, prerequisites = [[1,0]]
为例。
建图后：
0 -> 1
入度为：
indegree = [0, 1]
拓扑排序过程：
- 课程
0入度为0，入队 - 学完课程
0，visited = 1，课程1的入度减为0，入队 - 学完课程
1，visited = 2
visited == 2 == numCourses，返回 true。
示例 2
以：
numCourses = 2, prerequisites = [[1,0],[0,1]]
为例。
建图后：
0 -> 1
1 -> 0
入度为：
indegree = [1, 1]
两门课程的入度都不为 0，队列一开始就是空的，visited 保持为 0。
visited == 0 != 2，返回 false。
复杂度分析
解法一
建图遍历所有先修关系，拓扑排序中每个节点和每条边都被处理一次。
- 时间复杂度：
O(n + m)，其中n = numCourses，m = prerequisites.length - 空间复杂度：
O(n + m)，邻接表占O(n + m)，入度数组占O(n)
解法二
每个节点和每条边最多被访问一次。
- 时间复杂度：
O(n + m) - 空间复杂度：
O(n + m)，邻接表占O(n + m)，状态数组占O(n)
其中 n 是课程数，m 是先修关系的数量。
两种解法复杂度相同，拓扑排序（BFS）更直观、更容易记忆，是推荐写法。