2025-10-18：针对图的路径存在性查询Ⅰ。用go语言，给定 n 个节点

景点排名 2025年10月18日 20:01 0 admin

2025-10-18：针对图的路径存在性查询Ⅰ。用go语言，给定 n 个节点，编号 0 到 n-1；同时有一个长度为 n 的非降序数组 nums 和一个整数 maxDiff。

若两个下标 i 和 j 对应的数值之差的绝对值不超过 maxDiff，则在节点 i 与节点 j 之间加入一条无向边。

另外给出若干查询，每个查询是一个双元素数组 [u, v]，要求判断节点 u 与 v 是否能通过若干条边连通（是否存在一条从 u 到 v 的路径）。

输出一个布尔数组，表示每个查询的结果（能连通为 true，不能为 false）。

提示：由于 nums 已排序，可以线性扫描相邻元素，当相邻元素之差大于 maxDiff 时切断连通性；把连续不被切断的区间视为同一连通块，之后每个查询只需比较两点是否在同一块内（也可用并查集/DSU 来实现）。

1 <= n == nums.length <= 100000。

0 <= nums[i] <= 100000。

nums 按非递减顺序排序。

0 <= maxDiff <= 100000。

1 <= queries.length <= 100000。

queries[i] == [ui, vi]。

0 <= ui, vi < n。

题目来自力扣3532。

解决过程详细步骤

1. 初始化并查集（DSU）：

• 创建一个大小为 n 的父数组 fa，初始时每个节点的父节点指向自己，表示每个节点独立为一个连通分量。

2. 构建连通分量：

• 由于 nums 是非降序排序的，相邻节点的值差（即 nums[i+1] - nums[i]）是非负的，因此绝对值差就是差值本身。

• 线性扫描所有相邻节点对（从节点 0 和 1 开始，到节点 n-2 和 n-1 结束）。对于每个相邻对 (i, i+1)，计算 nums[i+1] - nums[i]：

• 如果差值 ≤ maxDiff，说明节点 i 和 i+1 之间应该有边，使用并查集的合并操作将它们合并到同一个连通分量中。

• 如果差值 > maxDiff，则不做处理，相当于切断了连通性，表示这里是一个连通分量的边界。

• 通过这一过程，所有值差不超过 maxDiff 的连续节点会被合并到同一个连通分量中，形成多个连续的连通块。

3. 处理查询：

• 对于每个查询 [u, v]：

• 使用并查集的查找操作（带路径压缩）分别找到节点 u 和 v 的根节点。

• 如果根节点相同，说明 u 和 v 在同一个连通分量中，即存在路径，返回 true；否则返回 false。

• 将所有查询结果收集到一个布尔数组中返回。

为什么这个过程是正确的？

• 由于 nums 已排序，连通分量必然由连续节点组成（除非值差超过 maxDiff）。合并相邻节点等价于构建这些连续连通块。

• 任何两个节点连通当且仅当它们属于同一个连通块，因为边只存在于值差不超过 maxDiff的节点之间，且连通性通过相邻节点传递。

• 并查集高效地维护了连通分量的合并和查询。

时间复杂度和空间复杂度

• 总时间复杂度：O(n α(n) + q α(n))，其中 n 是节点数，q 是查询数，α(n) 是反阿克曼函数（由于路径压缩，实际运行时间接近线性）。

初始化并查集：O(n)
构建连通分量：扫描 n-1 对相邻节点，每次合并操作平均 O(α(n))
处理查询：每个查询两次查找操作，平均 O(α(n))

• 总额外空间复杂度：O(n)，主要用于存储并查集的父数组 fa。其他变量（如循环索引等）使用常数空间。

Go完整代码如下：

package mainimport (    "fmt")func pathExistenceQueries(n int, nums []int, maxDiff int, queries [][]int) []bool {    // 初始化并查集    fa := make([]int, n)    for i := range fa {        fa[i] = i    }    // 查找函数，带路径压缩    var find func(int)int    find = func(i int)int {        if fa[i] == i {            return i        }        fa[i] = find(fa[i])        return fa[i]    }    // 合并函数    union := func(i, j int) {        x, y := find(i), find(j)        fa[y] = x    }    // 处理相邻节点    for i := 0; i < n-1; i++ {        if abs(nums[i+1]-nums[i]) <= maxDiff {            union(i, i+1)        }    }    // 处理查询    ans := make([]bool, len(queries))    for i, query := range queries {        u, v := query[0], query[1]        if find(u) == find(v) {            ans[i] = true        }    }    return ans}// 辅助函数：计算绝对值func abs(x int)int {    if x < 0 {        return -x    }    return x}func main() {    n := 2    nums := []int{1, 3}    maxDiff := 1    queries := [][]int{{0, 0}, {0, 1}}    result := pathExistenceQueries(n, nums, maxDiff, queries)    fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-from typing import Listdef pathExistenceQueries(n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:    # 初始化并查集    fa = list(range(n))        # 查找函数，带路径压缩    def find(i: int) -> int:        if fa[i] == i:            return i        fa[i] = find(fa[i])        return fa[i]        # 合并函数    def union(i: int, j: int):        x, y = find(i), find(j)        fa[y] = x        # 处理相邻节点    for i in range(n - 1):        if abs(nums[i + 1] - nums[i]) <= maxDiff:            union(i, i + 1)        # 处理查询    ans = [False] * len(queries)    for i, query in enumerate(queries):        u, v = query[0], query[1]        if find(u) == find(v):            ans[i] = True        return ans# 测试代码if __name__ == "__main__":    n = 2    nums = [1, 3]    maxDiff = 1    queries = [[0, 0], [0, 1]]    result = pathExistenceQueries(n, nums, maxDiff, queries)    print(result)  # 输出: [True, False]