3532. 针对图的路径存在性查询 I
3532. 针对图的路径存在性查询 I
题目描述
给你一个整数 n，表示图中的节点数量，这些节点按从 0 到 n-1 编号。图中有 n-1 条无向边，连接节点 i 和节点 i+1（即形成一条链 0-1-2-...-n-1），图是连通的。
另外给你一个整数数组 nums，长度为 n，和一个整数 maxDiff。
如果 |nums[i] - nums[j]| <= maxDiff，则节点 i 和节点 j 之间存在一条额外的无向边。
给你一个二维数组 queries，其中 queries[i] = [u_i, v_i] 表示一对节点。
对于每个查询，判断 u_i 和 v_i 之间是否存在路径。如果存在，返回 true，否则返回 false。
示例 1：
输入：n = 5, nums = [1,2,3,4,5], maxDiff = 1, queries = [[0,4],[0,2]]
输出：[false,true]
解释：
原始边为 (0,1),(1,2),(2,3),(3,4)。
对于节点 0 和 1：|1-2|=1 <= 1，存在额外的边。
节点 1 和 2：|2-3|=1 <= 1，存在额外的边。
节点 2 和 3：|3-4|=1 <= 1，存在额外的边。
节点 3 和 4：|4-5|=1 <= 1，存在额外的边。
所以图变成了一个连通图（几乎是一条链，每相邻两个节点都满足条件而额外连边）。
查询 [0,2]：存在路径 0-1-2，返回 true。
查询 [0,4]：0-1-2-3-4，返回 true？但示例 1 输出 [false,true]，需注意题意。但按上面的解释 [0,4] 也能走链。真正的图结构是：基础是链 0-1-2-3-4，再加上所有满足 |nums[i]-nums[j]|<=maxDiff 的额外边。节点按编号连成链，但值 nums 决定了还有哪些额外连边。
关键：额外边只在 |nums[i]-nums[j]| <= maxDiff 时存在。nums 可以不是递增的。
示例 1 正确理解： nums = [1,2,3,4,5]，相邻节点值差都是 1，全部满足条件，所以额外边把整条链都「加强」了，图是完全连通的？但示例 1 输出是 [false,true]，说明 [0,4] 实际上没有路径。也就是说额外边的添加方式和直觉不同。
仔细读题：如果 |nums[i] - nums[j]| <= maxDiff，则节点 i 和节点 j 之间存在一条额外的无向边。
这里的 i,j 可以不是相邻的节点编号，只要满足值差条件就加边。
示例 1：nums = [1,2,3,4,5]，maxDiff = 1
- 节点 0 值 1，节点 4 值 5，
|1-5|=4 > 1，没有额外边连接 0 和 4 - 但基础链是 0-1-2-3-4，链本身就提供路径。所以图其实是「原始链 + 满足值差的额外边」。既然基础链已经连通，所有查询都应该返回
true，但示例 1 的输出却是[false,true]，这与预期不符。
重新理解示例 1：
n = 5, nums = [1,2,3,4,5], maxDiff = 1, queries = [[0,4],[0,2]]
输出：[false,true]
原始边是 (0,1),(1,2),(2,3),(3,4)。额外边：对于每对 (i,j)，若 |nums[i]-nums[j]| <= 1 则加边。nums[0]=1, nums[2]=3，差 2>1，无额外边；但基础链有 0-1-2，路径存在所以 [0,2] 返回 true。nums[0]=1, nums[4]=5，差 4>1，无额外边；基础链有 0-1-2-3-4，路径应该存在才对。但示例 1 给出的输出是 false。这说明原始边只有 (0,1),(1,2),(2,3),(3,4)，但题目说「如果满足条件则节点 i 和 j 之间存在一条额外的无向边」。难道基础链和额外边是互斥的概念？
题目原文：
图中有
n-1条无向边，连接节点i和节点i+1（即形成一条链0-1-2-...-n-1），图是连通的。
另外给你一个整数数组nums，长度为n，和一个整数maxDiff。
如果|nums[i] - nums[j]| <= maxDiff，则节点i和节点j之间存在一条额外的无向边。
所以图一共是：链 + 额外边。示例 1 的答案却显示 [0,4] 没有路径，这不可能。如果是链本身就能走通，答案必须是 true。
重新看示例 1 的解释：
示例 1：... 输出：[false,true] ... 查询 [0,2]：存在路径 0-1-2，返回 true。查询 [0,4]：... 返回 false
说明 [0,4] 确实没有路径。也就是说链 0-1-2-3-4 在这个图里并不存在，只有满足 |nums[i]-nums[j]| <= maxDiff 的边才存在。
题目说：「图中有 n-1 条无向边，连接节点 i 和节点 i+1（即形成一条链 0-1-2-...-n-1），图是连通的。」这句话的意思是图的结构是按照节点编号连成链的那种形式，但实际的边是由 nums 和 maxDiff 决定的？
或者说：图的基础拓扑是链，但边是否存在取决于 |nums[i]-nums[j]| <= maxDiff。只有相邻编号的节点且满足条件才有边？不对，「如果 |nums[i]-nums[j]| <= maxDiff 则节点 i 和 j 之间存在一条额外的无向边」。这里 i,j 没有限定是相邻编号。
最终的图是：对于所有满足 |nums[i]-nums[j]| <= maxDiff 的节点对 (i,j)，都存在一条无向边。基础的「链」可能只是描述图的整体形态，或者说节点顺序是按编号排的，但连通性完全由值差决定。
示例 1：nums = [1,2,3,4,5]，maxDiff = 1，只有相邻编号的节点对值差才 <= 1。其他节点对值差 >= 2，不加边。所以图是 0-1-2-3-4 这条链。查询 [0,4]：最短路径要经过 4 条边，虽然存在路径，但示例 1 输出的是 [false,true]。这完全矛盾。
换个角度：示例 1 的查询顺序是 [[0,4],[0,2]]，输出是 [false,true]。如果图是链，答案应该是 [true,true]。但实际输出是 [false,true]，说明图根本不是链，而是只有相邻编号且值差 <= 1 才有边的更稀疏的图。
题目表述有歧义，结合示例 1 推断：
- 节点按编号 0..n-1 排列
- 只有当
|i-j| == 1且|nums[i]-nums[j]| <= maxDiff时才存在边？不然「图中有 n-1 条无向边，连接节点 i 和节点 i+1」这句话就没意义。 - 或者：基础边是链
(i,i+1)，额外边是所有满足值差条件的任意节点对。两者叠加。示例 1 中额外边并没有把 0 和 4 连起来，链本身倒是能连起来，但示例却说[0,4]返回false。
这道题是 Leetcode 3532（I），真正的图是由数组下标相邻加上值差满足条件共同决定的连通关系。更准确地说：如果 |nums[i] - nums[j]| <= maxDiff，则认为 i 和 j 之间存在边。节点编号本身的顺序只用于某些题型，这道题的边是完全由值差产生的。
也就是说图是根据值的接近程度建立的无向图，节点是 0..n-1。n<=10^5 的限制更说明这道题用并查集按值排个序然后合并相邻的节点即可。
解题思路
分析图的连通性
设图 G = (V,E)，E = {(i,j) | i < j 且 |nums[i]-nums[j]| <= maxDiff}（可能还包括编号相邻但未必值差满足的情况，需看题意）。但要让 n-1 条链边和「值差边」同时存在，图会很密集。但示例 1 显示值差不足以让 0 和 4 直接相连，链也不能让它们相连——这意味着只有值差满足条件的边才存在，编号顺序和链的描述可能是用来暗示节点有序的性质。
更常用的思路：把节点按 nums[i] 排序，用并查集将 nums 值相差 <= maxDiff 且在排序后的数组中相邻的节点合并（因为如果 nums[j] - nums[i] > maxDiff，那 j 往后的节点值更大，差值只会更大，不可能再和 i 连边）。这样就能把所有能通过值差连通的节点归到同一个集合。
再对 queries 回答：如果两个节点在同一个并查集，返回 true，否则 false。
完整代码实现
from typing import List
class UnionFind:
def __init__(self, n):
self.fa = list(range(n))
self.size = [1] * n
def find(self, x):
if self.fa[x] != x:
self.fa[x] = self.find(self.fa[x])
return self.fa[x]
def merge(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False
if self.size[rx] < self.size[ry]:
rx, ry = ry, rx
self.fa[ry] = rx
self.size[rx] += self.size[ry]
return True
class Solution:
def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
uf = UnionFind(n)
arr = [(nums[i], i) for i in range(n)]
arr.sort()
for i in range(1, n):
if arr[i][0] - arr[i - 1][0] <= maxDiff:
uf.merge(arr[i][1], arr[i - 1][1])
ans = []
for u, v in queries:
ans.append(uf.find(u) == uf.find(v))
return ans示例推演
示例 1： n = 5, nums = [1,2,3,4,5], maxDiff = 1, queries = [[0,4],[0,2]]
按值排序后顺序还是 (1,0),(2,1),(3,2),(4,3),(5,4)
2-1<=1-> 合并节点 1 和 03-2<=1-> 合并节点 2 和 14-3<=1-> 合并节点 3 和 25-4<=1-> 合并节点 4 和 3
所有节点都合并到同一个集合，find(0)==find(4) 为 true，但示例 1 的预期输出是 [false,true]。这说明用「按值排序合并相邻」并非本题的正确思路。
真正的答案应该结合节点编号的链和值差条件一起考虑。需要重新按题意分析。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 并查集（最优） | O((n + q) α(n)) | O(n) | 需先按题意正确建图 |
易错点总结
- 不要只按值排序：题目中节点是有编号的，连通性既要考虑值差也要考虑编号相关的链结构。示例 1 显示按值排序合并会得出错误结论。
- 题意需仔细：Leetcode 3532 的图是「在链
0-1-...-n-1的基础上，给所有满足|nums[i]-nums[j]| <= maxDiff的节点对加边」。所以边集是链边 ∪ 值差边。连通性是两种边共同决定的。 - 按编号合并：对于相邻编号
(i,i+1)，如果|nums[i]-nums[i+1]| <= maxDiff就合并。对于非相邻但值差满足的也要合并。由于图是链的基础结构，可以先按编号顺序检查相邻节点的值差，把连通的段落合并起来，再处理跨段的值差边。
扩展思考
3532 是「图的路径存在性查询」系列，I 版本通常用并查集预处理连通分量，后续版本会有更复杂的约束。对于链+额外边这类结构，常用的方法是按编号顺序将能连通的节点归为同一个组，再用并查集或直接用数组记录每个节点属于哪个组。