LeetCodehot 力扣热题100 课程表
题目背景
这个问题要求我们判断是否可以完成所有课程的学习。每门课程可能依赖其他课程作为前置课程，构成了一个有向图。我们需要确定是否存在环，若存在环，说明课程之间互相依赖，无法完成所有课程；如果不存在环，则说明可以完成所有课程。
思路解析
1. 图的构建
我们将课程之间的依赖关系视为一个有向图：
• 课程是图的节点。
• 前置课程之间的依赖关系是有向边。例如，如果课程 A 需要课程 B，则我们在图中添加一条从 B 到 A 的边。
2. DFS 检测环
要检查图中是否存在环，经典的方法是使用 深度优先搜索（DFS）：
• 正在访问的节点（颜色为 1）：表示该节点正在递归访问中，遇到这种节点意味着图中有环。
• 已访问的节点（颜色为 2）：表示该节点及其所有后续节点已经被访问过，且没有发现环。
• 未访问的节点（颜色为 0）：表示该节点尚未访问。
DFS 的步骤：
• 遍历每个课程，如果课程未访问过，就进行 DFS 检查。
• 如果在 DFS 过程中，发现已经有课程正在访问（即发现环），则返回 false。
• 如果所有课程都能够成功访问且没有发现环，返回 true。
3. 终止条件
• 如果 DFS 中发现环，直接返回 false，说明存在循环依赖。
• 如果 DFS 完成后没有发现环，则返回 true，说明可以完成所有课程。
具体运行步骤
假设有以下示例输入：
int numCourses = 4;
vector<vector<int>> prerequisites = {{1, 0}, {2, 1}, {3, 2}};
这表示有 4 门课程，依赖关系如下：
• 课程 1 依赖课程 0
• 课程 2 依赖课程 1
• 课程 3 依赖课程 2
步骤 1：图的构建
首先，我们构建一个图，表示课程的依赖关系：
• g[0] = [1]：课程 0 依赖课程 1
• g[1] = [2]：课程 1 依赖课程 2
• g[2] = [3]：课程 2 依赖课程 3
• g[3] = []：课程 3 没有任何依赖关系
vector<vector<int>> g(numCourses);
for (auto& p : prerequisites) {
g[p[1]].push_back(p[0]);
}
步骤 2：DFS 遍历图
接下来，我们使用 DFS 遍历图来检查是否存在环。我们使用一个 colors 数组来标记每个课程的状态：
• colors[i] == 0：课程 i 尚未访问
• colors[i] == 1：课程 i 正在访问中（在当前递归栈中）
• colors[i] == 2：课程 i 已访问完毕
对于每个课程，如果它尚未访问，则启动 DFS：
for (int i = 0; i < numCourses; i++) {
if (colors[i] == 0 && dfs(i, g, colors)) {
return false; // 如果发现环，返回 false
}
}
步骤 3：DFS 检查环
在 dfs 函数中，我们递归访问课程的前置课程。如果发现正在访问的课程，说明存在环；如果课程已经完全访问过，则跳过。
bool dfs(int x, vector<vector<int>>& g, vector<int>& colors) {
colors[x] = 1; // 当前课程 x 正在访问中
for (int y : g[x]) { // 遍历课程 x 的所有前置课程 y
if (colors[y] == 1 || (colors[y] == 0 && dfs(y, g, colors))) {
return true; // 如果发现了环：1) y 正在访问中；2) y 尚未访问且递归时发现环
}
}
colors[x] = 2; // 完全访问完课程 x
return false; // 没有发现环
}
代码实现
具体运行步骤
以 numCourses = 4 和 prerequisites = {{1, 0}, {2, 1}, {3, 2}} 为例，具体的运行步骤如下：
1. 构建图：
• g[0] = [1]
• g[1] = [2]
• g[2] = [3]
• g[3] = []
2. DFS 遍历图：
• 从课程 0 开始，检查它的前置课程，发现课程 1，继续递归。
• 课程 1 的前置课程是课程 2，继续递归。
• 课程 2 的前置课程是课程 3，继续递归。
• 课程 3 没有前置课程，返回并标记为已访问。
• 完成所有课程的遍历，发现没有环。
3. 返回 true：
• 所有课程都没有形成环，因此返回 true，说明可以完成所有课程。
时间复杂度
• 图构建：时间复杂度为 O(E)，其中 E 是 prerequisites 数组中的边数。
• DFS 遍历：每个课程和每条依赖边只会被访问一次，因此 DFS 的时间复杂度是 O(V + E)，其中 V 是课程数，E 是依赖关系数。
因此，总体时间复杂度是 O(V + E)，其中 V 是课程数，E 是依赖关系数。
好的，下面我会为你提供更加详细的运行步骤，并结合一个具体的示例进行演示，帮助你理解如何通过图的 DFS（深度优先搜索）来检测是否能完成所有课程。
题目示例
假设我们有 4 门课程，依赖关系为：
numCourses = 4;
prerequisites = {{1, 0}, {2, 1}, {3, 2}};
这表示：
• 课程 1 依赖于课程 0
• 课程 2 依赖于课程 1
• 课程 3 依赖于课程 2
目标是确定是否能够完成所有课程。如果有环（即课程之间存在循环依赖），则返回 false，否则返回 true。
步骤 1：构建图
首先，我们需要构建图。课程的依赖关系被表示为一个有向图，每个节点代表一门课程，每条边表示一门课程的前置课程。
对于 prerequisites = {{1, 0}, {2, 1}, {3, 2}}，图将如下构建：
• 课程 0 -> 课程 1 （课程 1 依赖课程 0）
• 课程 1 -> 课程 2 （课程 2 依赖课程 1）
• 课程 2 -> 课程 3 （课程 3 依赖课程 2）
最终图的结构是：
g[0] = [1] // 课程 0 -> 课程 1
g[1] = [2] // 课程 1 -> 课程 2
g[2] = [3] // 课程 2 -> 课程 3
g[3] = [] // 课程 3 没有依赖
步骤 2：DFS 遍历图
接下来，我们将使用 深度优先搜索（DFS） 来遍历图，并检测是否存在环。我们需要使用一个 colors 数组来标记课程的访问状态：
• 0 表示该课程尚未访问。
• 1 表示该课程正在访问中（即当前递归栈中的课程）。
• 2 表示该课程已完全访问过。
步骤 3：进行 DFS 遍历
初始化
1. 初始化 colors 数组：
vector<int> colors(numCourses, 0); // 初始值全为 0，表示所有课程都未访问
2. 调用 dfs(i) 来访问每个课程。如果在 DFS 中发现环，则返回 false；否则，返回 true。
具体的 DFS 过程
1. 从课程 0 开始进行 DFS：
• colors[0] 设置为 1，表示课程 0 正在访问中。
• 课程 0 依赖于课程 1，递归调用 dfs(1)。
2. 在 dfs(1) 中：
• colors[1] 设置为 1，表示课程 1 正在访问中。
• 课程 1 依赖于课程 2，递归调用 dfs(2)。
3. 在 dfs(2) 中：
• colors[2] 设置为 1，表示课程 2 正在访问中。
• 课程 2 依赖于课程 3，递归调用 dfs(3)。
4. 在 dfs(3) 中：
• colors[3] 设置为 1，表示课程 3 正在访问中。
• 课程 3 没有依赖课程，所以直接将 colors[3] 设置为 2，表示课程 3 完成访问。
5. 返回到 dfs(2)：
• 课程 2 完成访问，colors[2] 设置为 2。
• 返回到 dfs(1)。
6. 返回到 dfs(0)：
• 课程 0 完成访问，colors[0] 设置为 2。
• 所有课程都已完成访问。
步骤 4：结果判断
在整个 DFS 遍历过程中，如果没有发现环（即没有遇到 colors[x] == 1 的情况），则说明所有课程都可以完成。
最终，colors 数组的状态为：
colors = {2, 2, 2, 2}
所有课程的状态都为 2，表示它们都已完成访问，没有发现环，因此可以完成所有课程，返回 true。