题目描述补充

课程表Ⅰ

给定一个整数n，表示有n门课程，编号从1到n。再给定一个二维数组edges，其中edges[i] = [from_course, to_course]表示存在一门先修课关系，即在学习to_course之前必须先完成from_course。

现在请你判断是否存在一种学习顺序，使得可以学完所有课程。如果存在这样的顺序，则返回true；否则返回false。

注意：

• 课程中可能存在循环依赖。
• 输入的先修关系都是有效的，即from_course不会等于to_course。

示例

输入：

n = 2
edges = [[1, 0]]

输出：

true

解释：存在一种学习顺序，例如先学习课程0再学习课程1。

输入：

n = 2
edges = [[1, 0], [0, 1]]

输出：

false

解释：课程之间存在循环依赖，无法完成所有课程的学习。

PHP 示例代码

function canFinish($numCourses, $prerequisites) {
    $graph = array_fill(0, $numCourses, []);
    $visited = array_fill(0, $numCourses, 0); // 0: 未访问, 1: 访问中, 2: 已完成

    foreach ($prerequisites as $edge) {
        $graph[$edge[1]][] = $edge[0];
    }

    for ($i = 0; $i < $numCourses; $i++) {
        if (!dfs($i, $graph, $visited)) {
            return false;
        }
    }

    return true;

    function dfs($course, $graph, &$visited) {
        if ($visited[$course] == 1) {
            return false; // 发现环
        }

        if ($visited[$course] == 2) {
            return true; // 已访问过，无需再检查
        }

        $visited[$course] = 1;

        foreach ($graph[$course] as $preReq) {
            if (!dfs($preReq, $graph, $visited)) {
                return false;
            }
        }

        $visited[$course] = 2;
        return true;
    }
}

// 示例用法
$numCourses = 2;
$prerequisites = [[1, 0], [0, 1]];
echo canFinish($numCourses, $prerequisites) ? "true" : "false";

Python 示例代码

def canFinish(numCourses, prerequisites):
    graph = [[] for _ in range(numCourses)]
    visited = [0] * numCourses  # 0: 未访问, 1: 访问中, 2: 已完成

    for prereq in prerequisites:
        graph[prereq[1]].append(prereq[0])

    for i in range(numCourses):
        if not dfs(i, graph, visited):
            return False

    return True

def dfs(course, graph, visited):
    if visited[course] == 1:
        return False  # 发现环

    if visited[course] == 2:
        return True  # 已访问过，无需再检查

    visited[course] = 1

    for preReq in graph[course]:
        if not dfs(preReq, graph, visited):
            return False

    visited[course] = 2
    return True

# 示例用法
numCourses = 2
prerequisites = [[1, 0], [0, 1]]
print(canFinish(numCourses, prerequisites))

JavaScript 示例代码

function canFinish(numCourses, prerequisites) {
    const graph = new Array(numCourses).fill(null).map(() => []);
    const visited = new Array(numCourses).fill(0); // 0: 未访问, 1: 访问中, 2: 已完成

    for (const [to, from] of prerequisites) {
        graph[to].push(from);
    }

    for (let i = 0; i < numCourses; i++) {
        if (!dfs(i, graph, visited)) {
            return false;
        }
    }

    return true;

    function dfs(course, graph, visited) {
        if (visited[course] === 1) {
            return false; // 发现环
        }

        if (visited[course] === 2) {
            return true; // 已访问过，无需再检查
        }

        visited[course] = 1;

        for (const preReq of graph[course]) {
            if (!dfs(preReq, graph, visited)) {
                return false;
            }
        }

        visited[course] = 2;
        return true;
    }
}

// 示例用法
const numCourses = 2;
const prerequisites = [[1, 0], [0, 1]];
console.log(canFinish(numCourses, prerequisites));

码小课 网站中有更多关于算法和数据结构的相关内容分享给大家学习，包括更复杂的课程表问题、图论问题、深度优先搜索（DFS）和广度优先搜索（BFS）等算法的深入讲解和实战应用。