课程表

有些课必须先学完另一门才能开始。把课程表看成一张依赖图后，问题就变成了：这张有向图里是否存在无法打破的循环依赖？

问题与目标

LeetCode 207：课程表给出课程数和先修关系。[a,b] 表示学 a 之前必须先学 b，因此建图方向是 b → a。

例如 [[1,0],[2,0],[3,1],[3,2]]：先学 0，再学 1 和 2，最后才能学 3。返回能否完成全部课程，而不是必须返回某一种排课顺序。

入度就是尚未完成的先修要求

用邻接表保存“完成本课程后，哪些课程的条件会减少”，用入度记录每门课还依赖多少条先修关系。入度为 0 的课程可以立即开始。

把所有入度为 0 的课程放入队列。每取出一门，将它的后继入度减一；某个后继减到 0，就进入队列。最终处理数等于课程总数，才表示全部课程都能排进去。

为什么队列空了不一定成功

在例子中初始入度为 [0,1,1,2]。处理 0 后，1、2 的入度变成 0；处理完 1、2，3 的入度才变成 0。

如果有 0 → 1 → 0，两个节点都没有机会首先入队。即使图里还有能独立完成的其他课程，最终处理数仍会少于总数。不能只从某一个起点搜索后就宣布整张图无环。

C++17：拓扑排序

#include <queue>
#include <vector>

class Solution {
 public:
  bool canFinish(int num_courses, std::vector<std::vector<int>>& prerequisites) {
    std::vector<std::vector<int>> next(num_courses);
    std::vector<int> indegree(num_courses, 0);
    for (const auto& edge : prerequisites) {
      next[edge[1]].push_back(edge[0]);
      ++indegree[edge[0]];
    }
    std::queue<int> ready;
    for (int course = 0; course < num_courses; ++course) {
      if (indegree[course] == 0) ready.push(course);
    }
    int completed = 0;
    while (!ready.empty()) {
      const int course = ready.front();
      ready.pop();
      ++completed;
      for (int following : next[course]) {
        if (--indegree[following] == 0) ready.push(following);
      }
    }
    return completed == num_courses;
  }
};

输入沿用题目约定：每条关系恰有两个合法课程编号。通用数据导入接口还应先校验编号，不能把异常下标直接用于数组访问。

另一种判断：DFS 的三种状态

递归 DFS 将课程标记为未访问、当前路径中、已经处理完。沿边遇到“当前路径中”的节点才说明形成环；遇到已处理完的节点不代表有环。

#include <functional>
#include <vector>

bool canFinishDfs(int num_courses, const std::vector<std::vector<int>>& prerequisites) {
  std::vector<std::vector<int>> next(num_courses);
  for (const auto& edge : prerequisites) next[edge[1]].push_back(edge[0]);
  std::vector<int> state(num_courses, 0);
  std::function<bool(int)> visit = [&](int course) {
    if (state[course] == 1) return false;
    if (state[course] == 2) return true;
    state[course] = 1;
    for (int following : next[course]) {
      if (!visit(following)) return false;
    }
    state[course] = 2;
    return true;
  };
  for (int course = 0; course < num_courses; ++course) {
    if (!visit(course)) return false;
  }
  return true;
}

复杂度与边界

两种方法都以 O(V+E) 时间处理所有课程与关系，图和状态占 O(V+E) 空间。DFS 的最深调用链还会占 O(V) 栈空间，极长依赖链优先考虑迭代版拓扑排序。

没有依赖时所有课程都可入队；孤立课程也计入完成数；重复依赖若出现，必须在邻接表和入度中一致计数，不能只对一侧去重；自环直接构成循环。

常见误区

把 [a,b] 画成 a → b 会让解释与代码相反；把“访问过”当“正在当前路径里”会把共享后继误判成环；只检查队列是否清空则漏掉未处理的环中课程。