LeetCode 1462. 课程表 IV

2022-07-16 HGNULB 约 9 分钟

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

分类

题目描述

✅ 1462. 课程表 IV

题意分析

有 n 门编号 0 到 n-1 的课，prerequisites 给出若干「先修」关系 [a, b]，表示必须先修 a 才能修 b。然后给一批查询 [u, v]，逐个回答「u 是不是 v 的先修课」，返回布尔数组。

最关键的一句在题面里：先修关系是可传递的——a 是 b 的先修、b 是 c 的先修，那么 a 也是 c 的先修。所以问的不是「有没有一条直接的边」，而是「有没有一条有向路径」。这一句把题目从「查邻接表」升级成了「查可达性」。

约束给出了极强的信号：n <= 100，而查询数量可以到 $10^4$。两个数字合在一起说明——点数小得离谱，查询多得离谱。这意味着应该把所有代价压在预处理上，做成一张能 $O(1)$ 回答任意查询的表；而 $n = 100$ 让 $n^3 = 10^6$ 这种在别处不敢想的三重循环变得完全可以接受。反过来，若对每个查询单独跑一次搜索，最坏是 $10^4 \times (n + e)$，虽然本题也能过，但预处理的写法明显更契合数据形态。

题目还保证图无环（先修关系不能循环依赖），所以不需要判环，也不用担心可达性计算陷入死循环。另外要注意「u 是 v 的先修」是有向的：u → v 可达不代表 v → u 可达，查询里两个方向都可能出现。

边界：u == v 时按题意应为 false（自己不是自己的先修课），只要不给对角线置真就自然成立；prerequisites 为空时所有查询都是 false；查询里出现从未在先修关系中露面的课程编号也是合法的，答案自然为 false。

解法：传递闭包

核心思路

最直接的想法是把每个查询当成一次独立的图搜索：从 u 出发做 DFS 或 BFS，看能不能走到 v。单次是 $O(n + e)$，$10^4$ 个查询就是 $10^4 \times (n + e)$。这能过，但每次搜索都在重复探索同一片图区域——瓶颈就在这里：查询之间没有共享任何计算成果。

既然点数只有 100，所有「谁能到谁」的信息合起来也不过 $100 \times 100 = 10^4$ 个布尔值，完全存得下。于是把思路反过来：一次性把所有点对的可达性全算出来，之后每个查询就是一次数组下标访问。这张表就是有向图的传递闭包。

怎么算传递闭包？沿用 Floyd-Warshall 的思想。定义状态：reach[i][j] 为真，当且仅当存在一条从 i 到 j 的有向路径。初始时只把直接给出的边置真。

Floyd 的核心是对「中转点」做归纳。它的循环不变量是：当外层枚举到 k 时（k 从 0 递增），reach[i][j] 已经正确表示「只允许经过编号严格小于 k 的点作为中转，i 能否到达 j」。处理完 k 这一轮之后，中转点集合扩展为「编号小于 k+1」。

从 k 推到 k+1 只需要一条规则：新增的路径必然经过 k，因此可以被拆成「i 到 k」加上「k 到 j」两段，而这两段都只用编号小于 k 的中转点，正是上一轮已经算好的结果。于是转移是 reach[i][j] |= reach[i][k] && reach[k][j]。当 k 跑完全部 n 个点，中转点不再受限，reach 就是完整的传递闭包。

Floyd 的中转点 k 必须在最外层，因为每一轮是在上一轮允许的中转点集合上增加 k。若把 k 放到内层，一次遍历不再保证所有依赖链都已按阶段闭包，结果会依赖节点编号和扫描顺序。

解题步骤

开 n × n 的布尔矩阵 reach，全部为 false：注意不要把对角线 reach[i][i] 置真。最短路版本的 Floyd 要求 dist[i][i] = 0，但这里语义是「是不是先修课」，自己不是自己的先修课，置真会让 u == v 的查询错误地返回 true。这是从最短路模板迁移过来时最容易犯的错。

写入直接边：对每条 [a, b] 置 reach[a][b] = true。方向不能反——a 是 b 的先修，边是 a → b。重边直接覆盖，无需去重。

三重循环，k 在最外层：k 是中转点，i 是起点，j 是终点。顺序必须是 k → i → j。

中层剪枝：若 reach[i][k] 为假，则无论 j 是什么，经过 k 的路径都不存在，可以直接 continue 跳过整个内层循环。这不改变复杂度上界，但在稀疏图上能省掉绝大部分内层迭代，是很值得写的一行。

内层松弛：reach[k][j] 为真时置 reach[i][j] = true。这里用「或」的语义，只置真不置假——已经可达的点对不会因为某个中转点走不通而变回不可达。

逐个回答查询：res[t] = reach[q[0]][q[1]]，每次 $O(1)$。查询顺序即输出顺序，不能重排。

以 n = 5、prerequisites = [[0,1],[1,2],[2,3],[3,4]]（一条链 0→1→2→3→4）、queries = [[0,4],[4,0],[1,3],[3,1]] 走一遍。

初始化：只有链上的 4 条直接边为真，即 reach[0][1]、reach[1][2]、reach[2][3]、reach[3][4]。

k = 0：需要 reach[i][0] 为真的 i，但没有任何点能到达 0（0 是链头），中层剪枝全部跳过，矩阵不变。

k = 1：reach[i][1] 为真的只有 i = 0。内层看 reach[1][j]，此时为真的只有 j = 2。于是置 reach[0][2] = true。现在 0 能到 1、2。

k = 2：reach[i][2] 为真的有 i = 0、i = 1。reach[2][j] 为真的只有 j = 3。于是置 reach[0][3]、reach[1][3] 为真。

k = 3：reach[i][3] 为真的有 i = 0、1、2。reach[3][j] 为真的只有 j = 4。于是置 reach[0][4]、reach[1][4]、reach[2][4] 为真。

k = 4：4 是链尾，reach[4][j] 全假，内层不产生任何更新。

回答查询：[0,4] → reach[0][4] = true；[4,0] → reach[4][0] = false（方向相反，链上走不回去）；[1,3] → reach[1][3] = true；[3,1] → reach[3][1] = false。

返回 [true, false, true, false]。这个用例同时验证了三点：传递性被正确累积（0 到 4 隔着三个中转点也判对）、方向性没有被弄反、以及 k 从小到大枚举时链式关系被逐层扩散——注意 reach[0][4] 是在 k = 3 那一轮才被点亮的，它依赖 k = 2 轮算出的 reach[0][3]，这正是外层归纳不能打乱顺序的直接证据。

代码实现

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

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^3 + e + q)$。三重循环是 $O(n^3)$，n <= 100 时约 $10^6$ 次布尔运算，毫秒级；写入直接边是 $O(e)$；每个查询 $O(1)$，共 $O(q)$。相比「每个查询单独搜索」的 $O(q \cdot (n + e))$，当 q 远大于 n 时预处理明显更优，这正是本题数据形态所指向的方向。

空间复杂度：$O(n^2 + q)$，矩阵保存全部点对可达性，结果数组保存 $q$ 个查询答案；若不计返回值，额外空间为 $O(n^2)$。

关键点总结

看数据范围选算法：n <= 100 配上 $10^4$ 级查询，是「预处理全部答案 + $O(1)$ 查询」的典型信号。同样的题若把 n 放大到 $10^5$，就必须改成按查询搜索或按拓扑序做位图传播。

传递闭包 = 把 Floyd 的「加法取最小」换成「与运算取或」。识别出这个同构关系，就能把最短路模板直接迁移过来，这是图论题里非常高频的一次转译。

Floyd 的中转点 k 必须在最外层。这是整套算法的归纳骨架，i、j 的相对顺序无所谓，但 k 的位置动不得。被问到「为什么」时要能讲出「reach[i][k] 必须是上一轮的完整结果」。

对角线是否置真取决于题意，不能照搬最短路模板。本题「自己不是自己的先修课」，对角线必须保持 false。

中层的 if (!reach[i][k]) continue 是零成本优化，稀疏图上能砍掉大部分内层迭代，写出来能体现对常数的敏感。

易错点总结

把对角线 reach[i][i] 初始化为 true：查询 [2, 2] 会返回 true，而正确答案是 false。这是从最短路 Floyd 模板（dist[i][i] = 0）直接搬过来的典型后果。

边的方向写反，写成 reach[p[1]][p[0]] = true：prerequisites = [[0,1]]、查询 [0,1] 会返回 false、查询 [1,0] 返回 true，答案全部颠倒。

把中转点 k 放在内层循环：例如按 i → j → k 只扫一遍时，prerequisites = [[0,2],[2,3],[3,1]] 会先处理目标 j = 1，当时 0 → 3 尚未推出；之后即使得到 0 → 3 也不会回头更新 0 → 1，查询 [0,1] 错误返回 false。

用 reach[i][j] = reach[i][k] && reach[k][j] 而不是「只置真」：把原本已经为真的直接边冲成 false，prerequisites = [[0,1]] 在 k = 2 那一轮就会把 reach[0][1] 抹掉，查询 [0,1] 返回 false。

结果数组的顺序按查询内容排序或去重：题目要求输出与 queries 严格一一对应，任何重排都会让答案错位；重复查询也必须重复输出。

n 与实际出现的最大编号混淆，按 prerequisites 里出现过的编号开矩阵：n = 5 但先修关系只涉及 0~2 时，查询 [3, 4] 会数组越界。矩阵必须按题目给的 n 开。

相似题目

题目	难度	考察点
207. 课程表	中等	只问能否修完，即判断有向图是否有环，用入度队列或三色标记
210. 课程表 II	中等	要输出一个合法修课顺序，考察拓扑排序的构造而非可达性
1334. 阈值距离内邻居最少的城市	中等	同样是小 `n` 的 Floyd，但矩阵存的是距离，还要处理无穷大与并列取大编号
743. 网络延迟时间	中等	单源最短路，点数更大时应改用 Dijkstra 而非全源矩阵
399. 除法求值	中等	边带乘性权重，可达性之外还要沿路径累乘，可用带权并查集或 Floyd 变体
547. 省份数量	中等	无向图的连通性统计，用并查集或一次遍历即可，不需要点对级别的闭包