Problem

An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes, and the graph may not be connected.

Implement the DistanceLimitedPathsExist class:

  • DistanceLimitedPathsExist(int n, int[][] edgeList) Initializes the class with an undirected graph.
  • boolean query(int p, int q, int limit) Returns true if there exists a path from p to q such that each edge on the path has a distance strictly less than limit, and otherwise false.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

**Input**
["DistanceLimitedPathsExist", "query", "query", "query", "query"]
[[6, [[0, 2, 4], [0, 3, 2], [1, 2, 3], [2, 3, 1], [4, 5, 5]]], [2, 3, 2], [1, 3, 3], [2, 0, 3], [0, 5, 6]]
**Output**
[null, true, false, true, false]
**Explanation**
DistanceLimitedPathsExist distanceLimitedPathsExist = new DistanceLimitedPathsExist(6, [[0, 2, 4], [0, 3, 2], [1, 2, 3], [2, 3, 1], [4, 5, 5]]);
distanceLimitedPathsExist.query(2, 3, 2); // return true. There is an edge from 2 to 3 of distance 1, which is less than 2.
distanceLimitedPathsExist.query(1, 3, 3); // return false. There is no way to go from 1 to 3 with distances **strictly** less than 3.
distanceLimitedPathsExist.query(2, 0, 3); // return true. There is a way to go from 2 to 0 with distance < 3: travel from 2 to 3 to 0.
distanceLimitedPathsExist.query(0, 5, 6); // return false. There are no paths from 0 to 5.

Constraints:

  • 2 <= n <= 10^4
  • 0 <= edgeList.length <= 10^4
  • edgeList[i].length == 3
  • 0 <= ui, vi, p, q <= n-1
  • ui != vi
  • p != q
  • 1 <= disi, limit <= 10^9
  • At most 104 calls will be made to query.

Solution

Method 1 – Offline Union-Find with Query Sorting

Intuition

For each query, we want to know if there is a path between two nodes such that all edge weights are strictly less than a given limit. By sorting both the edges and the queries by weight/limit, we can use a union-find (DSU) structure to incrementally connect nodes as the limit increases, efficiently answering all queries.

Reasoning

By processing queries in order of increasing limit, and always adding all edges with weight less than the current limit to the union-find, we ensure that at each query, the union-find structure represents the connectivity for all edges with weight less than the limit. Thus, we can answer each query in nearly constant time after sorting.

Approach

  1. Store all edges and queries, and sort both by edge weight and query limit, respectively.
  2. Use a union-find (DSU) structure to keep track of connected components.
  3. For each query (in order of increasing limit):
    • Add all edges with weight less than the query’s limit to the union-find.
    • Check if the two nodes in the query are connected in the union-find.
  4. Return the answer for each query.

Edge cases:

  • No edges: only nodes themselves are connected.
  • Multiple edges between nodes: only the smallest matters for each limit.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class DistanceLimitedPathsExist {
    int[] par;
    int[] rank;
    List<int[]> edges;
    public DistanceLimitedPathsExist(int n, int[][] edgeList) {
        par = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) par[i] = i;
        edges = new ArrayList<>();
        for (int[] e : edgeList) edges.add(e);
        edges.sort(Comparator.comparingInt(a -> a[2]));
    }
    int find(int x) {
        if (par[x] != x) par[x] = find(par[x]);
        return par[x];
    }
    void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        if (rank[px] < rank[py]) par[px] = py;
        else if (rank[px] > rank[py]) par[py] = px;
        else { par[py] = px; rank[px]++; }
    }
    int idx = 0;
    public boolean query(int p, int q, int limit) {
        while (idx < edges.size() && edges.get(idx)[2] < limit) {
            union(edges.get(idx)[0], edges.get(idx)[1]);
            idx++;
        }
        return find(p) == find(q);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class DistanceLimitedPathsExist:
    def __init__(self, n: int, edgeList: list[list[int]]):
        self.par = list(range(n))
        self.rank = [0] * n
        self.edges = sorted(edgeList, key=lambda x: x[2])
        self.idx = 0
    def find(self, x: int) -> int:
        if self.par[x] != x:
            self.par[x] = self.find(self.par[x])
        return self.par[x]
    def union(self, x: int, y: int):
        px, py = self.find(x), self.find(y)
        if px == py: return
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
        elif self.rank[px] > self.rank[py]:
            self.par[py] = px
        else:
            self.par[py] = px
            self.rank[px] += 1
    def query(self, p: int, q: int, limit: int) -> bool:
        while self.idx < len(self.edges) and self.edges[self.idx][2] < limit:
            self.union(self.edges[self.idx][0], self.edges[self.idx][1])
            self.idx += 1
        return self.find(p) == self.find(q)

Complexity

  • ⏰ Time complexity: O((E + Q) * α(N)), where E is the number of edges, Q is the number of queries, and α is the inverse Ackermann function (nearly constant), as each union/find operation is nearly constant time.
  • 🧺 Space complexity: O(N + E), as we store the union-find structure and all edges.