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。