M3532.针对图的路径存在性查询I

disjoint set, https://leetcode.cn/problems/path-existence-queries-in-a-graph-i/description/

给你一个整数 n，表示图中的节点数量，这些节点按从 0 到 n - 1 编号。

同时给你一个长度为 n 的整数数组 nums，该数组按 非递减 顺序排序，以及一个整数 maxDiff。

如果满足 |nums[i] - nums[j]| <= maxDiff（即 nums[i] 和 nums[j] 的 绝对差 至多为 maxDiff），则节点 i 和节点 j 之间存在一条 无向边 。

此外，给你一个二维整数数组 queries。对于每个 queries[i] = [ui, vi]，需要判断节点 ui 和 vi 之间是否存在路径。

返回一个布尔数组 answer，其中 answer[i] 等于 true 表示在第 i 个查询中节点 ui 和 vi 之间存在路径，否则为 false。

示例 1：

输入: n = 2, nums = [1,3], maxDiff = 1, queries = [[0,0],[0,1]]

输出: [true,false]

解释:

查询 [0,0]：节点 0 有一条到自己的显然路径。
查询 [0,1]：节点 0 和节点 1 之间没有边，因为 |nums[0] - nums[1]| = |1 - 3| = 2，大于 maxDiff。
因此，在处理完所有查询后，最终答案为 [true, false]。

示例 2：

输入: n = 4, nums = [2,5,6,8], maxDiff = 2, queries = [[0,1],[0,2],[1,3],[2,3]]

输出: [false,false,true,true]

解释:

生成的图如下：

查询 [0,1]：节点 0 和节点 1 之间没有边，因为 |nums[0] - nums[1]| = |2 - 5| = 3，大于 maxDiff。
查询 [0,2]：节点 0 和节点 2 之间没有边，因为 |nums[0] - nums[2]| = |2 - 6| = 4，大于 maxDiff。
查询 [1,3]：节点 1 和节点 3 之间存在路径通过节点 2，因为 |nums[1] - nums[2]| = |5 - 6| = 1 和 |nums[2] - nums[3]| = |6 - 8| = 2，都小于等于 maxDiff。
查询 [2,3]：节点 2 和节点 3 之间有一条边，因为 |nums[2] - nums[3]| = |6 - 8| = 2，等于 maxDiff。
因此，在处理完所有查询后，最终答案为 [false, false, true, true]。

提示：

1 <= n == nums.length <= 105
0 <= nums[i] <= 105
nums 按 非递减 顺序排序。
0 <= maxDiff <= 10^5
1 <= queries.length <= 10^5
queries[i] == [ui, vi]
0 <= ui, vi < n

这个题目可以用「并查集」（Union Find）来高效处理！

因为 nums 是 非递减 排序的，所以如果 |nums[i] - nums[j]| <= maxDiff，节点 i 和 j 一定是相邻的或很近的。所以我们可以：

从左到右，只连接相邻节点 i 和 i+1，如果 nums[i+1] - nums[i] <= maxDiff。
用 并查集 把这些能连通的点合并在一起。
最后，对于每个查询 [u, v]，只需要判断 u 和 v 是否在同一个连通块里（也就是 find(u) == find(v)）。

这样，整体复杂度大概是 O(n + q)，能轻松应对 10^5 规模！

完整代码：

python

from typing import List

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]
    
    def union(self, x, y):
        self.parent[self.find(x)] = self.find(y)

class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
        uf = UnionFind(n)

        for i in range(n - 1):
            if nums[i+1] - nums[i] <= maxDiff:
                uf.union(i, i+1)

        res = []
        for u, v in queries:
            res.append(uf.find(u) == uf.find(v))
        return res

核心思想总结：

只在 nums[i] 和 nums[i+1] 之间建边（因为排序了，其他的不可能更近）。
并查集合并相邻可达节点。
查询就是快速判断是不是同一个集合。

【郭泓竹 24中文系】相邻差 > maxDiff 即断开，新建连通块；查询看两点块号是否相同

python

from typing import List

class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
        comp = [0] * n
        cur = 0
        for i in range(1, n):
            if nums[i] - nums[i - 1] > maxDiff:
                cur += 1
            comp[i] = cur
        return [comp[u] == comp[v] for u, v in queries]

【张洺瑜 24地空】还以为要建类，用完整的并查集做法。其实由于数组单调，所以只需要比较相邻两个数就可以将他们分成不同的组，用每个组的首位作记录，比较节点的记录值是否一致。

python

class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
        lst=[0]*len(nums)
        tmp=0
        for i in range(1,len(nums)):
            if nums[i]-nums[i-1]>maxDiff:
                tmp=i
            lst[i]=tmp
        ans=[False]*len(queries)
        for j,(x,y) in enumerate(queries):
            if lst[x]==lst[y]:
                ans[j]=True
        return ans

【郑涵予 24物理学院】这里数组已经被排好序了，所以只要直接判断相邻的两个数之差会不会大于maxDiff就行，如果大于就把后一个数归入下一组.接下来只要判断查询的数是不是在同一个组里就行.(用时约8min)

python

class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
        a=[0]*n
        pos=0
        for i in range(n-1):
            if nums[i+1]-nums[i]<=maxDiff:
                a[i]=a[i+1]=pos
            else:
                a[i]=pos
                pos+=1
                a[i+1]=pos
        m=len(queries)
        ans=[False]*m
        for i in range(m):
            u,v=queries[i][0],queries[i][1]
            if a[u]==a[v]:
                ans[i]=True
            else:
                ans[i]=False
        return ans

M3532.针对图的路径存在性查询I ​

M3532.针对图的路径存在性查询I