LeetCode 1462. 课程表 IV

2022-07-16 HGNULB 约 5 分钟

文章信息 6 个分类 · 4 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 字节

标签

深度优先搜索 广度优先搜索 图 拓扑排序

题目描述

✅ 1462. 课程表 IV

题意分析

每条先修关系 [a, b] 表示学习课程 b 前必须先学课程 a，即有向边 a → b。对于每个查询 [u, v]，判断 u 是否是 v 的先修课，既包含直接关系，也包含经过其他课程传递得到的间接关系。

问题不是返回某个可行学习顺序。两门没有依赖的课也可以在某个顺序中一前一后，但这不代表前者是后者的先修课；必须确实存在从 u 到 v 的有向路径。题目保证依赖图无环，各查询按输入顺序分别返回布尔结果。

解法：传递闭包

核心思路

[!blue]

查询数量较多，而课程数较小，可以先计算任意两门课之间是否可达，再把每次查询变成一次查表。定义 reach[i][j] 表示存在从课程 i 到课程 j 的先修路径，初始只写入给出的直接边。

逐个允许课程作为路径的中转点。开始第 k 轮前，表中记录的是只允许编号小于 k 的课程出现在路径中间时的可达性。加入中转点 k 后，一条路径要么不经过它，沿用旧状态；要么经过它，拆成 i → k 和 k → j 两段。

只要这两段都存在，就能确认 i → j，所以转移是把 reach[i][k] && reach[k][j] 与旧 reach[i][j] 做逻辑或。更新只增加可达关系，不能清除之前通过其他中转点已经找到的路径。

中转点必须放在最外层，才能在一轮结束后统一得到“允许前 k + 1 个中转点”的完整结果。若只把 k 放到最内层扫一遍，某条所需的间接路径可能还没计算出来，后面变成可达时却不再回头更新原查询对。

代码在 i 不能到达当前 k 时跳过整段内循环，因为此时不存在经过 k 的新路径。题目无环，对角线不需要设真，课程也不会通过非空路径回到自己。所有中转点处理完后，表中就包含全部直接与间接先修关系。

解题步骤

1. 创建全为假的 n × n 可达表，按 [先修课, 后续课] 的方向写入直接边。
2. 最外层依次枚举中转点 k。
3. 枚举起点 i，若 i 无法到达 k，跳过这个起点的本轮扩展。
4. 否则枚举终点 j，当 k 能到达 j 时，将 reach[i][j] 置真。
5. 处理完全部中转点后，按原顺序返回每个查询对应的表项。

代码实现

class Solution {
    public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) {
        // reach[i][j]：i 到 j 是否存在有向路径。对角线保持 false，自己不是自己的先修课。
        boolean[][] reach = new boolean[n][n];

        for (int[] p : prerequisites) {
            reach[p[0]][p[1]] = true;
        }

        // Floyd 求传递闭包：中转点 k 必须在最外层，否则归纳前提被破坏。
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                // i 到不了 k，经过 k 的路径全都不存在，整层内层循环可跳过。
                if (!reach[i][k]) {
                    continue;
                }

                for (int j = 0; j < n; j++) {
                    if (reach[k][j]) {
                        reach[i][j] = true;
                    }
                }
            }
        }

        List<Boolean> res = new ArrayList<>(queries.length);

        for (int[] q : queries) {
            res.add(reach[q[0]][q[1]]);
        }

        return res;
    }
}

func checkIfPrerequisite(n int, prerequisites [][]int, queries [][]int) []bool {
    // reach[i][j]：i 到 j 是否存在有向路径。对角线保持 false，自己不是自己的先修课。
    reach := make([][]bool, n)
    for i := 0; i < n; i++ {
        reach[i] = make([]bool, n)
    }
    for _, p := range prerequisites {
        reach[p[0]][p[1]] = true
    }

    // Floyd 求传递闭包：中转点 k 必须在最外层，否则归纳前提被破坏。
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            // i 到不了 k，经过 k 的路径全都不存在，整层内层循环可跳过。
            if !reach[i][k] {
                continue
            }
            for j := 0; j < n; j++ {
                if reach[k][j] {
                    reach[i][j] = true
                }
            }
        }
    }

    res := make([]bool, len(queries))
    for i, q := range queries {
        res[i] = reach[q[0]][q[1]]
    }
    return res
}

复杂度分析

• 时间复杂度：O(n³ + e + q)。写入 e 条直接边，三层循环计算传递闭包，最后处理 q 个常数时间查询。
• 空间复杂度：可达表占 O(n²)，返回的查询结果另占 O(q)。

关键点总结

[!green]

• 先修关系是有方向的可达性，不是拓扑排序中的偶然先后。
• 每轮增加一个可用中转点，给三层循环提供明确的阶段不变量。
• 新路径与旧路径取并集，已有可达关系始终保留。
• 一次预处理服务全部查询，查询阶段不再重复搜索。

易错点总结

[!yellow]

• 把输入边方向写反：本题 [a, b] 表示 a 是 b 的先修，而不是相反。
• 只检查直接关系表：会漏掉经过多门课传递的依赖。
• 用拓扑排名比较代替可达性：排名靠前不代表存在先修路径。
• 中转点放最内层且只扫描一次：依赖关系可能在使用之后才被算出，造成间接路径遗漏。
• 用本轮两段条件覆盖旧值：当前中转不可用不代表两点原本不可达，必须保留旧的真值。
• 把边当成无向连接：反向到达通常不成立，不能对称写入。

相似题目

题目	难度	关联与区别
210. 课程表 II	中等	拓扑顺序只能说明某种合法先后，u排在v前不代表存在先修路径，本题必须维护传递可达性。
207. 课程表	中等	原题只判整个依赖图是否无环，本题对很多指定节点对回答真实依赖关系。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/62228335

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！