leetcode：207. 课程表

题目

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
prerequisites[i] 中的所有课程对 互不相同。

示例：

  1. 输入：numCourses = 2, prerequisites = [[1,0]]
  2. 输出：true
  3. 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
  1. 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
  2. 输出：false
  3. 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

解答 & 代码

拓扑排序 - 有向图的环检测算法 - BFS 深度优先遍历（邻接表、入度表）

  1. class Solution {
  2. public:
  3.     bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
  4.         // 邻接表，存储图结构（边）。eg. graph[i] = [j, k]，代表存在边 ij，ik
  5.         vector<vector<int>> graph(numCourses);
  6.         // 入度数组，eg. indeg[i] 代表节点（课程） i 的入度
  7.         vector<int> indeg(numCourses, 0);
  8.         for(int i = 0; i < prerequisites.size(); ++i)
  9.         {
  10.             int preCourse = prerequisites[i][1];
  11.             int nextCourse = prerequisites[i][0];
  12.             graph[preCourse].push_back(nextCourse);
  13.             ++indeg[nextCourse];
  14.         }
  16.         // 课程队列，存入入度为 0 的节点（课程）
  17.         queue<int> courseQ;
  18.         // 初始化，将所有入度为 0 的节点都存入队列
  19.         for(int i = 0; i < numCourses; ++i)
  20.         {
  21.             if(indeg[i] == 0)
  22.                 courseQ.push(i);
  23.         }
  25.         int count = 0;        // 已遍历的节点个数
  26.         // 开始 BFS 广度优先遍历节点
  27.         while(!courseQ.empty())
  28.         {
  29.             // 当前遍历的节点
  30.             int curCourse = courseQ.front();
  31.             courseQ.pop();
  32.             ++count;        // 已遍历的节点个数 +1
  34.             // 删除以 curCourse 节点为起点的所有边（将对应的终点的入度 -1）
  35.             for(int i = 0; i < graph[curCourse].size(); ++i)
  36.             {
  37.                 int nextCourse = graph[curCourse][i];    // 这条边的终点
  38.                 --indeg[nextCourse];                    // 终点入度 -1
  39.                 // 如果终点入度变为 0，则存入队列
  40.                 if(indeg[nextCourse] == 0)
  41.                     courseQ.push(nextCourse);
  42.             }
  43.         }
  45.         // 如果最终已遍历的节点数 = 课程总数，说明不存在循环，返回 true；否则返回 false
  46.         return count == numCourses;
  47.     }
  48. };

复杂度分析：设图的节点数（即课程数）为 N，设边数 M

  • 时间复杂度 O(N + M)：遍历一个图需要访问所有节点和边
  • 空间复杂度 O(N + M)：
    • 邻接表 graph 长为 N，并且存储了 M 条边的数据，因此空间复杂度 O(N + M)
    • 入度数组 indeg 空间复杂度 O(N)
    • 队列 courseQ 空间复杂度 O(N)

执行结果：

  1. 执行结果：通过
  3. 执行用时：16 ms, 在所有 C++ 提交中击败了 88.57% 的用户
  4. 内存消耗：12.8 MB, 在所有 C++ 提交中击败了 94.24% 的用户