题目描述

假设你正在设计一个大学课程表系统，其中课程之间可能存在先修关系。例如，学习课程B之前必须先完成课程A。现在给你一个课程数量n和一个二维数组prerequisites，其中prerequisites[i] = [ai, bi]表示学习课程bi之前必须先完成课程ai。

你的任务是编写一个函数来判断是否存在一个合理的学习顺序，使得所有的课程都可以被学习。如果存在这样的顺序，则返回true；否则返回false。

注意：

1. 输入的课程数量n是一个正整数。
2. prerequisites中的每个课程对[ai, bi]都是唯一的，并且保证bi不会在ai的先修课程列表中。

示例

示例 1:

输入: n = 2, prerequisites = [[1,0]]
输出: true
解释: 存在一种学习顺序 [0,1]，其中 0 是 1 的先修课程。

示例 2:

输入: n = 2, prerequisites = [[1,0],[0,1]]
输出: false
解释: 不存在一种学习顺序可以同时满足 0 是 1 的先修课程和 1 是 0 的先修课程。

PHP 示例代码

function canFinish($numCourses, $prerequisites) {
    // 构建邻接表表示课程之间的先修关系
    $graph = array_fill(0, $numCourses, []);
    for ($i = 0; $i < count($prerequisites); $i++) {
        $graph[$prerequisites[$i][1]][] = $prerequisites[$i][0];
    }

    // 初始化访问状态数组
    $visited = array_fill(0, $numCourses, 0); // 0: 未访问, 1: 正在访问, 2: 已访问

    // 遍历每个课程，检查是否存在环
    for ($i = 0; $i < $numCourses; $i++) {
        if (hasCycle($graph, $visited, $i)) {
            return false;
        }
    }

    return true;
}

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

    if ($visited[$course] == 2) {
        // 课程已访问过，无环
        return false;
    }

    $visited[$course] = 1; // 标记为正在访问

    foreach ($graph[$course] as $preReq) {
        if (hasCycle($graph, $visited, $preReq)) {
            return true;
        }
    }

    $visited[$course] = 2; // 标记为已访问

    return false;
}

Python 示例代码

from collections import defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    for pre, course in prerequisites:
        graph[course].append(pre)

    visited = [0] * numCourses  # 0: 未访问, 1: 正在访问, 2: 已访问

    def dfs(course):
        if visited[course] == 1:
            return True
        if visited[course] == 2:
            return False

        visited[course] = 1
        for pre in graph[course]:
            if dfs(pre):
                return True

        visited[course] = 2
        return False

    for i in range(numCourses):
        if dfs(i):
            return False

    return True

JavaScript 示例代码

function canFinish(numCourses, prerequisites) {
    const graph = new Array(numCourses).fill(0).map(() => []);
    for (const [pre, course] of prerequisites) {
        graph[course].push(pre);
    }

    const visited = new Array(numCourses).fill(0); // 0: 未访问, 1: 正在访问, 2: 已访问

    function dfs(course) {
        if (visited[course] === 1) {
            return true;
        }
        if (visited[course] === 2) {
            return false;
        }

        visited[course] = 1;

        for (const pre of graph[course]) {
            if (dfs(pre)) {
                return true;
            }
        }

        visited[course] = 2;
        return false;
    }

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

    return true;
}

以上代码均实现了检查课程表中是否存在合理的学习顺序的逻辑，使用了深度优先搜索（DFS）来检测图中是否存在环，从而判断是否存在合理的学习顺序。