You are given an undirected, connected graph with n nodes labeled from 0 to n - 1. The graph is described by the list edgeList, where each element is a triplet [u, v, w] indicating an edge between nodes u and v with length w.
You are also given a list of queries queries, where each query is a triplet [p, q, limit]. For each query, determine if there exists a path between nodes p and q such that every edge on the path has a length strictly less than limit.
Constraints:
105 nodes, edges, and queries.
At first glance, you might consider running a shortest-path or BFS/DFS for each query, filtering out edges with weights above the limit. However, this approach quickly becomes too slow for large graphs and many queries because it effectively re-traverses the graph for each query.
To optimize, notice that the only property that matters for a query is connectivity using edges below a certain threshold. If you could "precompute" which nodes are connected via edges less than any given weight, you could answer each query quickly.
This insight points to using a Union-Find (Disjoint Set Union, DSU) data structure. By sorting both the edges and the queries by weight, we can incrementally build up connected components as the limit increases, answering each query efficiently.
We use a combination of sorting and the Union-Find data structure to efficiently answer all queries:
edgeList in ascending order of edge weight. This allows us to process edges in increasing order.
limit value.
limit), add all edges whose weight is less than the current limit to the Union-Find structure.p and q are in the same set (i.e., connected via edges all less than limit).Why Union-Find? Union-Find allows us to efficiently merge connected components and check connectivity in nearly constant time (amortized), which is crucial for large datasets.
Suppose:
n = 5
edgeList = [[0,1,2], [1,2,4], [2,3,6], [3,4,8]]
queries = [[0,4,5], [0,4,10]]
[0,4,5]
[0,4,10]
limit: O(Q * (N + E))O(E \log E)O(Q \log Q)O((E + Q) * α(N)), where α is the inverse Ackermann function (practically constant for all reasonable N).O((E + Q) \log (E + Q))O(N + E + Q) for storing edges, queries, and DSU arrays.The key insight is to process all queries efficiently by incrementally building connectivity using Union-Find as edge weight thresholds increase. By sorting both edges and queries, and only updating connectivity as needed, we avoid redundant work and achieve a highly efficient solution even for large graphs and many queries. This approach elegantly leverages the power of disjoint-set data structures and sorting to answer each query in nearly constant time after preprocessing.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px != py:
self.parent[py] = px
class Solution:
def distanceLimitedPathsExist(self, n, edgeList, queries):
edgeList.sort(key=lambda x: x[2])
queries_with_idx = [(p, q, limit, idx) for idx, (p, q, limit) in enumerate(queries)]
queries_with_idx.sort(key=lambda x: x[2])
uf = UnionFind(n)
res = [False] * len(queries)
i = 0
for p, q, limit, idx in queries_with_idx:
while i < len(edgeList) and edgeList[i][2] < limit:
uf.union(edgeList[i][0], edgeList[i][1])
i += 1
if uf.find(p) == uf.find(q):
res[idx] = True
return res
class UnionFind {
public:
vector<int> parent;
UnionFind(int n) : parent(n) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(int x, int y) {
parent[find(x)] = find(y);
}
};
class Solution {
public:
vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
sort(edgeList.begin(), edgeList.end(), [](const vector<int>& a, const vector<int>& b) {
return a[2] < b[2];
});
int q = queries.size();
vector<tuple<int,int,int,int>> qs;
for (int i = 0; i < q; ++i) {
qs.emplace_back(queries[i][0], queries[i][1], queries[i][2], i);
}
sort(qs.begin(), qs.end(), [](const auto& a, const auto& b) {
return get<2>(a) < get<2>(b);
});
UnionFind uf(n);
vector<bool> res(q, false);
int i = 0;
for (auto& [p, qv, limit, idx] : qs) {
while (i < edgeList.size() && edgeList[i][2] < limit) {
uf.unite(edgeList[i][0], edgeList[i][1]);
++i;
}
if (uf.find(p) == uf.find(qv)) res[idx] = true;
}
return res;
}
};
class UnionFind {
int[] parent;
public UnionFind(int n) {
parent = new int[n];
for (int i = 0; i < n; ++i) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
parent[find(x)] = find(y);
}
}
class Solution {
public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
Arrays.sort(edgeList, (a, b) -> Integer.compare(a[2], b[2]));
int q = queries.length;
int[][] queriesWithIndex = new int[q][4];
for (int i = 0; i < q; ++i) {
queriesWithIndex[i][0] = queries[i][0];
queriesWithIndex[i][1] = queries[i][1];
queriesWithIndex[i][2] = queries[i][2];
queriesWithIndex[i][3] = i;
}
Arrays.sort(queriesWithIndex, (a, b) -> Integer.compare(a[2], b[2]));
UnionFind uf = new UnionFind(n);
boolean[] res = new boolean[q];
int i = 0;
for (int[] query : queriesWithIndex) {
int p = query[0], qv = query[1], limit = query[2], idx = query[3];
while (i < edgeList.length && edgeList[i][2] < limit) {
uf.union(edgeList[i][0], edgeList[i][1]);
++i;
}
if (uf.find(p) == uf.find(qv)) res[idx] = true;
}
return res;
}
}
class UnionFind {
constructor(n) {
this.parent = Array.from({length: n}, (_, i) => i);
}
find(x) {
if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
return this.parent[x];
}
union(x, y) {
this.parent[this.find(x)] = this.find(y);
}
}
var distanceLimitedPathsExist = function(n, edgeList, queries) {
edgeList.sort((a, b) => a[2] - b[2]);
let queriesWithIndex = queries.map((q, idx) => [...q, idx]);
queriesWithIndex.sort((a, b) => a[2] - b[2]);
let uf = new UnionFind(n);
let res = Array(queries.length).fill(false);
let i = 0;
for (let [p, qv, limit, idx] of queriesWithIndex) {
while (i < edgeList.length && edgeList[i][2] < limit) {
uf.union(edgeList[i][0], edgeList[i][1]);
i++;
}
if (uf.find(p) === uf.find(qv)) res[idx] = true;
}
return res;
};