课程表

题目要求

这个问题是关于课程规划的，可以抽象为一个有向图的问题，其中每个课程可以看作是图中的一个节点，而先修课程的要求可以看作是节点之间的有向边。具体来说：

有 numCourses 门课程，它们被编号为 0 到 numCourses - 1。
先修课程的要求通过一个数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] 表示要学习课程 ai 必须先学习课程 bi。
任务是判断是否有可能完成所有课程的学习。

解题思路

要解决这个问题，可以采用以下步骤：

构建图表示：首先，我们需要将课程和先修关系转换成图的表示方法。这可以通过创建一个邻接表来实现，邻接表中的每个索引对应一个课程，每个索引处的列表包含了所有先修课程。
检测环：在有向图中，如果存在环，则意味着存在循环依赖，即某些课程的先修课程直接或间接地依赖于它们自己，这种情况下是不可能完成所有课程的学习的。检测环可以通过深度优先搜索（DFS）来实现。
深度优先搜索（DFS）：对于图中的每一个节点（课程），执行 DFS，过程中维护一个访问状态的数组，该数组记录了每个节点的三种状态：未访问、访问中、已访问。访问中的状态用于检测环。如果在 DFS 过程中遇到一个访问中的节点，说明存在环。
拓扑排序：如果图中无环，那么可以进行拓扑排序。拓扑排序是对有向无环图（DAG）的顶点的一种线性排序，使得对于任何一条有向边 (u, v)，顶点 u 都在顶点 v 之前。如果能够生成一种拓扑排序，则意味着可以完成所有课程的学习。
返回结果：如果在 DFS 过程中没有检测到环，那么返回 true，表示可以完成所有课程的学习。如果检测到环，则返回 false。

通过上述步骤，我们可以判断是否可能完成所有课程的学习。这个问题实质上是在检查有向图是否有环，也就是检查是否可以进行拓扑排序。

Golang 版本

package main

import "fmt"

func canFinish(numCourses int, prerequisites [][]int) bool {
    // 构建图的邻接表
    graph := make([][]int, numCourses)
    for _, pre := range prerequisites {
        graph[pre[1]] = append(graph[pre[1]], pre[0])
    }

    // 记录访问状态的数组，0 未访问，1 访问中，2 已访问
    visited := make([]int, numCourses)

    // 定义 DFS 函数，用于检测图中是否有环
    var dfs func(i int) bool
    dfs = func(i int) bool {
        if visited[i] == 1 { // 访问中的节点再次被访问，表示有环
            return false
        }
        if visited[i] == 2 { // 已访问的节点无需再次访问
            return true
        }

        visited[i] = 1 // 将节点标记为访问中
        for _, v := range graph[i] {
            if !dfs(v) { // 如果从节点 v 开始的 DFS 发现环，则返回 false
                return false
            }
        }
        visited[i] = 2 // 将节点标记为已访问
        return true
    }

    // 对每个节点执行 DFS
    for i := 0; i < numCourses; i++ {
        if !dfs(i) {
            return false
        }
    }
    return true
}

func main() {
    numCourses := 4
    prerequisites := [][]int{{1, 0}, {2, 1}, {3, 2}}
    if canFinish(numCourses, prerequisites) {
        fmt.Println("可以完成所有课程的学习")
    } else {
        fmt.Println("无法完成所有课程的学习")
    }
}

这段代码定义了一个 canFinish 函数，它接受课程总数和先修课程要求作为参数，返回一个布尔值表示是否可以完成所有课程的学习。主函数 main 中给出了一个示例调用。

C++版本

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> visit(numCourses, 0);

        // 构建图的邻接表
        for (const auto& pre : prerequisites) {
            graph[pre[1]].push_back(pre[0]);
        }

        // 检测是否有环
        for (int i = 0; i < numCourses; ++i) {
            if (!dfs(graph, visit, i)) {
                return false;
            }
        }
        return true;
    }

private:
    bool dfs(const vector<vector<int>>& graph, vector<int>& visit, int i) {
        if (visit[i] == 1) return false; // 如果节点在本轮DFS中被第二次访问，则说明有环
        if (visit[i] == 2) return true;  // 如果已经访问过，不需要再次访问

        visit[i] = 1; // 标记为访问中
        for (int j : graph[i]) {
            if (!dfs(graph, visit, j)) return false;
        }
        visit[i] = 2; // 标记为已访问
        return true;
    }
};

int main() {
    Solution solution;
    int numCourses = 4;
    vector<vector<int>> prerequisites = {{1, 0}, {2, 1}, {3, 2}};

    if (solution.canFinish(numCourses, prerequisites)) {
        cout << "可以完成所有课程的学习" << endl;
    } else {
        cout << "无法完成所有课程的学习" << endl;
    }

    return 0;
}

这段 C++ 代码定义了一个 Solution 类，其中包含了 canFinish 方法，用于判断是否可以完成所有课程的学习。main 函数中创建了一个 Solution 对象，并调用了 canFinish 方法，传入了课程总数和先修课程要求作为参数，然后输出了相应的结果。

Python 版本

from collections import defaultdict

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        # 创建图的邻接表
        graph = defaultdict(list)
        for course, pre in prerequisites:
            graph[pre].append(course)

        # 访问状态标记，0=未访问，1=访问中，2=已访问
        visit = [0] * numCourses

        # 深度优先搜索检测环
        def dfs(i):
            if visit[i] == 1:  # 访问中的节点再次被访问，表示有环
                return False
            if visit[i] == 2:  # 已访问的节点无需再次访问
                return True

            visit[i] = 1  # 标记为访问中
            for j in graph[i]:
                if not dfs(j):
                    return False
            visit[i] = 2  # 标记为已访问
            return True

        # 对每个节点尝试执行DFS
        for i in range(numCourses):
            if not dfs(i):
                return False
        return True

# 示例
numCourses = 4
prerequisites = [[1, 0], [2, 1], [3, 2]]
solution = Solution()
print("可以完成所有课程的学习" if solution.canFinish(numCourses, prerequisites) else "无法完成所有课程的学习")

这段 Python 代码定义了一个 Solution 类，其中包含了 canFinish 方法，用于判断是否可以完成所有课程的学习。在 canFinish 方法中，首先构建了课程的邻接表，然后通过深度优先搜索（DFS）检测图中是否存在环。如果不存在环，则可以完成所有课程的学习。最后，代码中给出了一个示例用于测试这个方法。

Java 版本

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] pair : prerequisites) {
            graph.get(pair[1]).add(pair[0]);
        }

        int[] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(graph, visited, i)) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(List<List<Integer>> graph, int[] visited, int course) {
        if (visited[course] == 1) return false; // cycle detected
        if (visited[course] == 2) return true; // already checked

        visited[course] = 1; // mark as visiting
        for (int nextCourse : graph.get(course)) {
            if (!dfs(graph, visited, nextCourse)) {
                return false;
            }
        }
        visited[course] = 2; // mark as visited
        return true;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int numCourses = 4;
        int[][] prerequisites = {{1, 0}, {2, 1}, {3, 2}};

        System.out.println(solution.canFinish(numCourses, prerequisites) ? "可以完成所有课程的学习" : "无法完成所有课程的学习");
    }
}

这段 Java 代码定义了一个 Solution 类，其中包含了 canFinish 方法，用于判断是否可以完成所有课程的学习。在 canFinish 方法中，首先构建了课程的邻接表，然后通过深度优先搜索（DFS）检测图中是否存在环。如果不存在环，则可以完成所有课程的学习。main 方法提供了一个示例，用于测试 canFinish 方法。

Rust 版本

use std::collections::VecDeque;

fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
    let mut graph = vec![vec![]; num_courses as usize];
    let mut in_degree = vec![0; num_courses as usize];

    // 构建图并计算所有节点的入度
    for pair in prerequisites {
        graph[pair[1] as usize].push(pair[0] as usize);
        in_degree[pair[0] as usize] += 1;
    }

    // 使用队列进行拓扑排序
    let mut queue: VecDeque<usize> = VecDeque::new();
    for i in 0..in_degree.len() {
        if in_degree[i] == 0 {
            queue.push_back(i);
        }
    }

    let mut count = 0;
    while let Some(course) = queue.pop_front() {
        count += 1;
        for &next_course in &graph[course] {
            in_degree[next_course] -= 1;
            if in_degree[next_course] == 0 {
                queue.push_back(next_course);
            }
        }
    }

    count == num_courses as usize
}

fn main() {
    let num_courses = 4;
    let prerequisites = vec![vec![1, 0], vec![2, 1], vec![3, 2]];
    println!("{}", if can_finish(num_courses, prerequisites) {
        "可以完成所有课程的学习"
    } else {
        "无法完成所有课程的学习"
    });
}

这段 Rust 代码实现了一个检查是否可以完成所有课程的函数 can_finish。它首先构建了一个图的邻接表和一个记录每个节点入度的数组。然后使用拓扑排序的方法，通过一个队列来处理所有入度为 0 的节点。如果最终处理的节点数量等于课程总数，说明没有环，可以完成所有课程的学习。在 main 函数中提供了一个示例来测试这个功能。

总结

上述代码片段展示了如何使用不同编程语言实现一个用于检测给定课程安排是否可行的算法。核心思想是使用图论中的拓扑排序来确定是否可以完成所有课程。拓扑排序是一种对有向图的顶点进行排序的方法，使得对于每一条有向边 (u, v)，顶点 u 都在顶点 v 之前。这种排序只有在图中没有有向环的情况下才可能。

在这个特定的问题中，课程可以被看作是图的顶点，而某些课程需要作为先决条件的其他课程可以被看作是顶点之间的有向边。算法的目标是检查这个有向图是否有环。如果有环，那么至少有一个课程的先决条件无法满足，因此不可能完成所有课程的学习。

不同语言的实现细节如下：

Python: 使用字典来构建邻接表，并通过递归的深度优先搜索（DFS）来检测环。
Java: 使用邻接表和一个访问状态数组来进行 DFS，并通过状态变化来检测环。
Rust: 使用邻接表和入度数组来实现拓扑排序，通过队列来处理所有入度为 0 的节点，并检测是否所有节点都被处理，从而判断是否有环。

在所有这些实现中，关键步骤是构建图，并通过图的遍历来检测环。如果能够进行拓扑排序，即所有节点都被处理，那么就可以完成所有课程的学习。如果在某个点无法继续进行拓扑排序（因为存在环），那么就不可能完成所有课程的学习。

hot-100