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

English Version

题目描述

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

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

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

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

返回一个布尔数组 answer，其中 answer[i] 等于 true 表示在第 i 个查询中节点 u_i 和 v_i 之间存在路径，否则为 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 <= 10⁵
0 <= nums[i] <= 10⁵
nums 按 非递减 顺序排序。
0 <= maxDiff <= 10⁵
1 <= queries.length <= 10⁵
queries[i] == [u_i, v_i]
0 <= u_i, v_i < n

解法

方法一：分组

根据题目描述，同一个连通分量的节点编号，一定是连续的。因此，我们可以用一个数组 $g$ 来记录每个节点所在的连通分量编号，用一个变量 $\textit{cnt}$ 来记录当前连通分量的编号。遍历 $\textit{nums}$ 数组，如果当前节点和前一个节点的差值大于 $\textit{maxDiff}$，则说明当前节点和前一个节点不在同一个连通分量中，我们就将 $\textit{cnt}$ 加 1。然后，我们将当前节点的连通分量编号赋值为 $\textit{cnt}$。

最后，对于每个查询 $(u, v)$，我们只需要判断 $g[u]$ 和 $g[v]$ 是否相等即可，如果相等，则说明 $u$ 和 $v$ 在同一个连通分量中，那么第 $i$ 个查询的答案就是 $\text{true}$，否则就是 $\text{false}$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是 $\textit{nums}$ 数组的长度。

Python3

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

Java

class Solution {
    public boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
        int[] g = new int[n];
        int cnt = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] - nums[i - 1] > maxDiff) {
                cnt++;
            }
            g[i] = cnt;
        }

        int m = queries.length;
        boolean[] ans = new boolean[m];
        for (int i = 0; i < m; ++i) {
            int u = queries[i][0];
            int v = queries[i][1];
            ans[i] = g[u] == g[v];
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<bool> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries) {
        vector<int> g(n);
        int cnt = 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] - nums[i - 1] > maxDiff) {
                ++cnt;
            }
            g[i] = cnt;
        }

        vector<bool> ans;
        for (const auto& q : queries) {
            int u = q[0], v = q[1];
            ans.push_back(g[u] == g[v]);
        }
        return ans;
    }
};

Go

func pathExistenceQueries(n int, nums []int, maxDiff int, queries [][]int) (ans []bool) {
	g := make([]int, n)
	cnt := 0
	for i := 1; i < n; i++ {
		if nums[i]-nums[i-1] > maxDiff {
			cnt++
		}
		g[i] = cnt
	}

	for _, q := range queries {
		u, v := q[0], q[1]
		ans = append(ans, g[u] == g[v])
	}
	return
}

TypeScript

function pathExistenceQueries(
    n: number,
    nums: number[],
    maxDiff: number,
    queries: number[][],
): boolean[] {
    const g: number[] = Array(n).fill(0);
    let cnt = 0;

    for (let i = 1; i < n; ++i) {
        if (nums[i] - nums[i - 1] > maxDiff) {
            ++cnt;
        }
        g[i] = cnt;
    }

    return queries.map(([u, v]) => g[u] === g[v]);
}