207. 课程表

题目链接：207. 课程表

题目描述

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

核心思考：有向图的拓扑排序（DFS 染色法检测环）

完成课程表的问题，本质上是判断一个有向图中是否存在环。如果存在环（即 A 依赖 B，B 又依赖于 A），那么这些课程永远无法被正常修完。

1. 图的表示：首先将输入的先修关系数组转换为邻接表 grid，方便深度优先搜索。
2. 三色标记法（Coloring Algorithm）：
   使用一个数组 colors 来记录每个节点的访问状态：
   • 状态 0 (未访问)：节点尚未进入搜索流。
   • 状态 1 (正在访问)：节点已进入当前递归深度流中，但尚未完成对其所有邻居的探查。如果搜索过程中遇到了状态 1 的邻居，则说明发现了环。
   • 状态 2 (已访问)：节点及其所有下游邻居都已安全探查完毕，确认不在任何环路中。
3. DFS 流程：
   • 遍历每个节点。如果是未访问状态，调用 DFS。
   • 在 DFS 中，先将节点设为 1。
   • 遍历邻居：若邻居处于状态 1，返回 True（有环）；若邻居处于状态 0 且下层探测到了环，也返回 True。
   • 探访结束，将状态设为 2。

如果遍历完所有节点都没有检测出环，说明图是一个有向无环图 (DAG)，即可以完成选课。

解题思路 (Python)

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # 1. 构造邻接表
        grid = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            grid[b].append(a)

        # 0: 未访问, 1: 正在访问（递归栈中）, 2: 已访问完成
        colors = [0] * numCourses

        def dfs(x):
            # 将当前节点设为正在访问
            colors[x] = 1
            for y in grid[x]:
                # 如果遇到正在访问的邻居，说明探测到环
                if colors[y] == 1:
                    return True
                # 继续向未访问过的邻居深挖
                if colors[y] == 0 and dfs(y):
                    return True
            # 访问结束，设为已完成状态
            colors[x] = 2
            return False

        # 对每一个初始节点进行探测
        for i, c in enumerate(colors):
            if c == 0 and dfs(i):
                # 如果 DFS 发现任何一个方向存在环，则无法完成
                return False
        return True

复杂度分析

• 时间复杂度：$O(V + E)$，其中 $V = numCourses$ 为课程数量，$E$ 为先修关系（边）的数量。每个节点和每条边在 DFS 过程中仅被处理常数次。
• 空间复杂度：$O(V + E)$。主要由存储邻接表的空间和递归扫描时产生的栈空间组成。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

m n
a11 a12 a13 ... a1n
a21 a22 a23 ... a2n
...
am1 am2 am3 ... amn

第一行输入矩阵的行数 m 和列数 n，随后输入 m 行 n 列的矩阵元素。

完整代码：

import sys

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    # 1. 构造邻接表
    grid = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        grid[b].append(a)

    # 0: 未访问, 1: 正在访问（递归栈中）, 2: 已访问完成
    colors = [0] * numCourses

    def dfs(x):
        # 将当前节点设为正在访问
        colors[x] = 1
        for y in grid[x]:
            # 如果遇到正在访问的邻居，说明探测到环
            if colors[y] == 1:
                return True
            # 继续向未访问过的邻居深挖
            if colors[y] == 0 and dfs(y):
                return True
        # 访问结束，设为已完成状态
        colors[x] = 2
        return False

    # 对每一个初始节点进行探测
    for i, c in enumerate(colors):
        if c == 0 and dfs(i):
            # 如果 DFS 发现任何一个方向存在环，则无法完成
            return False
    return True

def main():
    data = sys.stdin.read().strip().split()
    m, n = int(data[0]), int(data[1])
    idx = 2
    matrix = []
    for i in range(m):
        row = list(map(int, data[idx:idx+n]))
        matrix.append(row)
        idx += n

    sol = Solution()
    result = sol.canFinish(matrix)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

echo -e "3 3\n1 2 3\n4 5 6\n7 8 9" | python solution.py