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

福大大架构师每日一题

发布于 2025-12-18 14:39:43

180

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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 main

import (
    "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 List

def 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]