原题链接🔗：课程表
难度：中等⭐️⭐️
题目
你这个学期必须选修 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]中的所有课程对 互不相同
拓扑排序
拓扑排序是图论中的一个概念，它对有向无环图（DAG，Directed Acyclic Graph）中的顶点进行线性排序，使得对于任何一条有向边
U -> V，顶点U都在顶点V的前面。这种排序不是唯一的。拓扑排序常用于任务调度、课程规划等场景。以下是拓扑排序的一般步骤：
计算所有顶点的入度：入度是指有多少条边指向该顶点。对于图中的每个顶点，初始化一个计数器来记录入度。
将所有入度为0的顶点加入队列：入度为
0的顶点表示没有依赖，可以首先进行排序。处理队列中的顶点：
- 从队列中移除一个顶点，并将其加入到拓扑排序的结果列表中。
- 遍历该顶点的所有邻接点，将每个邻接点的入度减1（因为它们的一个依赖已经完成）。
- 如果某个邻接点的入度变为
0,将其加入队列。重复步骤3，直到队列为空。
检查环：如果拓扑排序的结果列表中的顶点数量等于原始图中的顶点数量，则图中没有环；否则，存在环，无法完成拓扑排序。
拓扑排序的算法可以用多种方式实现，包括Kahn算法和DFS（深度优先搜索）。
拓扑排序的时间复杂度通常是 O(V+E)，其中 V 是顶点数，E 是边数。空间复杂度为 O(V)，用于存储访问状态和排序结果。
题解
- 解题思路：
LeetCode 上的 “课程表” 问题（问题编号207）是一个典型的图论问题，主要考察了图的深度优先搜索（DFS）和拓扑排序的应用。
以下是这个问题的解题思路：
理解问题：首先，明确题目要求我们判断是否能够完成所有课程的学习。这等价于判断图中是否存在环，因为如果存在环，则表示有课程无法满足其所有先修条件。
构建图：根据给定的先修关系列表 prerequisites 构建一个有向图。可以使用邻接表来表示这个图，其中每个节点代表一门课程，边表示先修关系。
检测环：使用深度优先搜索（DFS）来检测图中是否存在环。在DFS过程中，使用两个集合来记录访问状态：
- visited：记录已经访问过的节点。
- recStack（递归栈）：记录当前递归路径上的节点，用于检测环。
DFS逻辑：
- 对于每个未访问的节点，执行DFS。
- 如果当前节点已经在 recStack 中，表示找到了一个环，返回 false。
- 如果当前节点已经访问过，并且不在 recStack 中，可以跳过。
- 将当前节点加入 visited 和 recStack。
- 对当前节点的所有邻接节点递归执行DFS。
- 递归返回后，将当前节点从 recStack 中移除。
拓扑排序：如果所有节点都可以通过DFS访问且没有检测到环，那么图是可拓扑排序的，即可以完成所有课程的学习。
- 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.
- 代码仓库地址：canFinish
