课程表

题面

你这个学期必须选修 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 <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

分析

• 显然，这个问题是拓扑排序问题

• 可以构造一个有向图，如果有向图中存在环路，说明无法完成课程的学习

• 代码实现

  #include <iostream>
  #include <queue>
  #include <unordered_map>
  #include <vector>
  using namespace std;
  
  class Solution {
  public:
      /**
       * @brief 判断是否能完成所有课程（检测有向图是否存在环）
       * @param numCourses 课程总数（节点数）
       * @param prerequisites 课程依赖关系，prerequisites[i] = [a, b]
       * 表示修a前必须先修b（有向边 b → a）
       * @return bool 无环则返回true（能完成），有环则返回false（无法完成）
       */
      bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
          // 1.
          // 构建邻接表：key是前驱课程，value是该课程修完后可修的后续课程列表（有向图）
          std::unordered_map<int, vector<int>> graph;
          // 2. 入度数组：inDegree[i]表示课程i的前驱课程数量（即有多少条边指向i）
          vector<int> inDegree(numCourses, 0);
  
          // 3. 初始化邻接表和入度数组
          for (vector<int> prerequisite : prerequisites) {
              int course = prerequisite[0];    // 当前课程（后继节点）
              int preCourse = prerequisite[1]; // 前置课程（前驱节点）
              inDegree[course]++;              // 后继课程入度+1
              graph[preCourse].push_back(
                  course); // 邻接表添加边：preCourse → course
          }
  
          // 4.
          // 初始化队列：将所有入度为0的课程（无前置依赖）加入队列（拓扑排序的起点）
          queue<int> que;
          for (int i = 0; i < numCourses; i++) {
              if (inDegree[i] == 0) {
                  que.push(i);
              }
          }
  
          int processed = 0; // 记录已处理的课程数
          // 5. 拓扑排序核心：逐步移除入度为0的节点，更新后续节点的入度
          while (!que.empty()) {
              // 优化：移除分层遍历的cur_size，直接处理单个节点
              int curCourse = que.front();
              que.pop();
              processed++; // 处理一个课程，计数+1
  
              // 遍历当前课程的所有后续课程，更新入度
              for (int nextCourse : graph[curCourse]) { // 范围for更简洁
                  if (--inDegree[nextCourse] ==
                      0) { // 先减1，再判断是否为0（简化代码）
                      que.push(nextCourse);
                  }
              }
          }
  
          return processed == numCourses; // 已处理数等于总课程数 → 无环
      }
  };

• 进一步地，可以给出课程表的拓扑排序结果

  class Solution {
  public:
      vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
          std::unordered_map<int, vector<int>> graph;
          vector<int> inDegree(numCourses, 0);
          vector<int> res;
          for (vector<int> prerequisite : prerequisites) {
              int course = prerequisite[0];    // 当前课程（后继节点）
              int preCourse = prerequisite[1]; // 前置课程（前驱节点）
              inDegree[course]++;              // 后继课程入度+1
              graph[preCourse].push_back(
                  course); // 邻接表添加边：preCourse → course
          }
  
          queue<int> que;
          for (int i = 0; i < numCourses; i++) {
              if (inDegree[i] == 0) {
                  que.push(i);
              }
          }
  
          int processed = 0; // 记录已处理的课程数
          while (!que.empty()) {
              int curCourse = que.front();
              que.pop();
              res.push_back(curCourse);
              processed++;                              // 处理一个课程，计数+1
              for (int nextCourse : graph[curCourse]) { // 范围for更简洁
                  if (--inDegree[nextCourse] == 0) {
                      que.push(nextCourse);
                  }
              }
          }
          if (processed != numCourses)
              res = {};
  
          return res;
      }
  };

DFS

• 课程表问题本质是检测有向图是否存在环，DFS 的核心逻辑是

• 状态标记：为每个节点（课程）标记三种状态，避免重复遍历和检测环路：

  • 0：未访问过；
  • 1：正在访问中（处于当前 DFS 递归栈中）；
  • 2：已访问完成（所有后续节点都遍历过，无环）。

• 递归遍历：对每个未访问的节点，递归遍历其所有后续节点：

  • 若遇到状态为1的节点 → 说明存在环（当前递归栈中重复访问，形成环路）；
  • 若所有后续节点都遍历完成且无环 → 标记当前节点为2；

• 结果判断：若所有节点遍历后都无环 → 可完成课程；否则不可完成

• 代码实现

  class Solution {
  public:
      // 三色标记：0未访问，1正在访问（递归栈中），2已访问
      void dfs(vector<vector<int>>& next, vector<int>& visited, int i, bool& hasCircle) {
          if (hasCircle) return;
          
          visited[i] = 1;  // 标记为正在访问
          for (int post : next[i]) {
              if (visited[post] == 1) {       // 遇到递归栈中的点 → 有环
                  hasCircle = true;
                  return;
              }
              if (visited[post] == 0) {       // 未访问过，继续DFS
                  dfs(next, visited, post, hasCircle);
              }
          }
          
          visited[i] = 2;  // 递归结束，标记为已访问
      }
  
      bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
          vector<int> visited(numCourses, 0);
          vector<vector<int>> next(numCourses);
          
          // 构建邻接表：pre[1] → pre[0]
          for (auto& pre : prerequisites) {
              next[pre[1]].push_back(pre[0]);
          }
  
          bool hasCircle = false;
          for (int i = 0; i < numCourses; i++) {
              if (visited[i] == 0) {        // 未访问过才DFS
                  dfs(next, visited, i, hasCircle);
              }
          }
          return !hasCircle;  // 无环返回true，可以修完
      }
  };

• 简洁代码实现

  class Solution {
  public:
      bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
          vector<vector<int>> g(numCourses);
          for (auto& p : prerequisites) {
              g[p[1]].push_back(p[0]);
          }
  
          vector<int> colors(numCourses);
          // 返回 true 表示找到了环
          auto dfs = [&](this auto&& dfs, int x) -> bool {
              colors[x] = 1; // x 正在访问中
              for (int y : g[x]) {
                  // 情况一：colors[y] == 1，表示发生循环依赖，找到了环
                  // 情况二：colors[y] == 0，未知，继续递归 y 获取信息
                  // 情况三：colors[y] == 2，继续递归 y 只会重蹈覆辙，和之前一样无法找到环
                  if (colors[y] == 1 || colors[y] == 0 && dfs(y)) {
                      return true; // 找到了环
                  }
              }
              colors[x] = 2; // x 完全访问完毕，从 x 出发无法找到环
              return false; // 没有找到环
          };
  
          for (int i = 0; i < numCourses; i++) {
              if (colors[i] == 0 && dfs(i)) {
                  return false; // 有环
              }
          }
          return true; // 没有环
      }
  };