LeetCode 算法：课程表 c++

原题链接🔗：课程表
难度：中等⭐️⭐️

题目

你这个学期必须选修 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] 中的所有课程对 互不相同

拓扑排序

拓扑排序是图论中的一个概念，它对有向无环图（DAG，Directed Acyclic Graph）中的顶点进行线性排序，使得对于任何一条有向边 U -> V，顶点 U 都在顶点 V 的前面。这种排序不是唯一的。拓扑排序常用于任务调度、课程规划等场景。

以下是拓扑排序的一般步骤：

1. 计算所有顶点的入度：入度是指有多少条边指向该顶点。对于图中的每个顶点，初始化一个计数器来记录入度。

2. 将所有入度为0的顶点加入队列：入度为0的顶点表示没有依赖，可以首先进行排序。

3. 处理队列中的顶点：

   • 从队列中移除一个顶点，并将其加入到拓扑排序的结果列表中。
   • 遍历该顶点的所有邻接点，将每个邻接点的入度减1（因为它们的一个依赖已经完成）。
   • 如果某个邻接点的入度变为0,将其加入队列。

4. 重复步骤3，直到队列为空。

5. 检查环：如果拓扑排序的结果列表中的顶点数量等于原始图中的顶点数量，则图中没有环；否则，存在环，无法完成拓扑排序。

拓扑排序的算法可以用多种方式实现，包括Kahn算法和DFS（深度优先搜索）。

拓扑排序的时间复杂度通常是 O(V+E)，其中 V 是顶点数，E 是边数。空间复杂度为 O(V)，用于存储访问状态和排序结果。

题解

1. 解题思路：

LeetCode 上的 “课程表” 问题（问题编号207）是一个典型的图论问题，主要考察了图的深度优先搜索（DFS）和拓扑排序的应用。
以下是这个问题的解题思路：

• 理解问题：首先，明确题目要求我们判断是否能够完成所有课程的学习。这等价于判断图中是否存在环，因为如果存在环，则表示有课程无法满足其所有先修条件。

• 构建图：根据给定的先修关系列表 prerequisites 构建一个有向图。可以使用邻接表来表示这个图，其中每个节点代表一门课程，边表示先修关系。

• 检测环：使用深度优先搜索（DFS）来检测图中是否存在环。在DFS过程中，使用两个集合来记录访问状态：

  • visited：记录已经访问过的节点。
  • recStack（递归栈）：记录当前递归路径上的节点，用于检测环。

• DFS逻辑：

  • 对于每个未访问的节点，执行DFS。
  • 如果当前节点已经在 recStack 中，表示找到了一个环，返回 false。
  • 如果当前节点已经访问过，并且不在 recStack 中，可以跳过。
  • 将当前节点加入 visited 和 recStack。
  • 对当前节点的所有邻接节点递归执行DFS。
  • 递归返回后，将当前节点从 recStack 中移除。

• 拓扑排序：如果所有节点都可以通过DFS访问且没有检测到环，那么图是可拓扑排序的，即可以完成所有课程的学习。

2. c++ demo：

#include <iostream>
#include <vector>
#include <queue>using namespace std;class Solution {
public:bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {vector<int> indegrees(numCourses, 0);vector<vector<int>> graph(numCourses);// 构建图并计算入度for (auto& pre : prerequisites) {graph[pre.first].push_back(pre.second);indegrees[pre.second]++;}// 拓扑排序vector<int> topsort;queue<int> q;for (int i = 0; i < numCourses; ++i) {if (indegrees[i] == 0) {q.push(i);}}while (!q.empty()) {int course = q.front();q.pop();topsort.push_back(course);for (int pre : graph[course]) {indegrees[pre]--;if (indegrees[pre] == 0) {q.push(pre);}}}// 如果所有课程都被排序了，图中没有环return topsort.size() == numCourses;}
};int main() {Solution solution;// 测试用例vector<pair<int, int>> prerequisites = { {1, 0}, {0, 1} };int numCourses = 4;bool result = solution.canFinish(numCourses, prerequisites);if (result) {cout << "It is possible to finish all courses." << endl;}else {cout << "It is not possible to finish all courses." << endl;}return 0;
}

• 输出结果：

It is not possible to finish all courses.

3. 代码仓库地址：canFinish