LeetCode 解題筆記：3532. Path Existence Queries in a Graph I

作者：王一哲
日期：2026年7月9日


LeetCode 題目連結：3532. Path Existence Queries in a Graph I

解題想法

中等難度題。題目給一個整數 $n$，代表共有 $n$ 個節點，編號為 $0$ 到 $n-1$。給一個長度為 $n$ 的陣列 $nums$，代表每個節點的值，而且 $nums$ 的值為非嚴格遞增，節點 $i$ 的值大於等於節點 $i-1$ 的值。給一個整數 $maxDiff$，代表兩個節點如果有道路連接，節點的最大差值。最後給一個二維陣列 $queries$，代表每次查詢的節點編號，如果兩個節點有連通回傳 True，反之回傳 False。
由於 $nums$ 的值為非嚴格遞增，如果要檢查兩個節點是否相連，只要檢查相鄰的節點即可。我另外自訂一個併查集類別，用一個 for 迴圈掃過所有的節點一次，$i = 1$ 到 $i = n-1$，每次檢查 $nums[i] - nums[i-1] \leq maxDiff$ 是否成立，如果條件成立就將兩個節點相連。於併查集類別之中自訂函式 is_unite，檢查任意兩個節點是否連通，用來處理 $queries$ 的多次查詢。

Python 程式碼

Runtime: 323 ms, beats 30.16%. Memory: 49.45 MB, beats 80.16%.

# 自訂併查集類別
class DisjointSetUnion:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.sz = [1] * n
    
    def rfind(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.rfind(self.parent[x])
        return self.parent[x]
    
    def unite(self, u, v):
        root_u, root_v = self.rfind(u), self.rfind(v)
        if root_u != root_v:
            if self.sz[root_u] < self.sz[root_v]:
                root_u, root_v = root_v, root_u
            self.sz[root_u] += self.sz[root_v]
            self.parent[root_v] = root_u
            return True
        return False

    def is_unite(self, u, v):
        root_u, root_v = self.rfind(u), self.rfind(v)
        return root_u == root_v

class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[bool]:
        dsu = DisjointSetUnion(n)  # 併查集物件
        for u in range(1, n):
            diff = nums[u] - nums[u-1]
            if diff <= maxDiff:
                dsu.unite(u, u-1)
        
        ans = []  # 答案
        for u, v in queries:
            ans.append(dsu.is_unite(u, v))
        return ans

C++ 程式碼

Runtime: 25 ms, beats 49.04%. Memory: 228.77 MB, beats 55.07%.

class DisjointSetUnion {
private:
    int n;
    vector<int> parent, sz;

public:
    DisjointSetUnion(int x) {
        n = x;
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        sz.assign(n, 1);
    }

    int rfind(int x) {
        if (parent[x] == x) return x;
        parent[x] = rfind(parent[x]);
        return parent[x];
    }

    bool unite(int u, int v) {
        int root_u = rfind(u), root_v = rfind(v);
        if (root_u != root_v) {
            if (sz[root_u] < sz[root_v]) swap(root_u, root_v);
            sz[root_u] += sz[root_v];
            parent[root_v] = root_u;
            return true;
        }
        return false;
    }

    bool is_unite(int u, int v) {
        int root_u = rfind(u), root_v = rfind(v);
        return root_u == root_v;
    }
};

class Solution {
public:
    vector<bool> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries) {
        DisjointSetUnion dsu(n);
        for(int u = 1; u < n; u++) {
            int diff = nums[u] - nums[u-1];
            if (diff <= maxDiff) dsu.unite(u, u-1);
        }

        int m = (int)queries.size();
        vector<bool> ans (m);
        for(int i = 0; i < m; i++) {
            if (dsu.is_unite(queries[i][0], queries[i][1])) {
                ans[i] = true;
            }
        }
        return ans;
    }
};