Formatted question description: https://leetcode.ca/all/1724.html
1724. Checking Existence of Edge Length Limited Paths II
Level
Hard
Description
An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [u_i, v_i, dis_i] denotes an edge between nodes u_i and v_i with distance dis_i. 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)Returnstrueif there exists a path fromptoqsuch that each edge on the path has a distance strictly less thanlimit, and otherwisefalse.
Example 1:
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^40 <= edgeList.length <= 10^4edgeList[i].length == 30 <= u_i, v_i, p, q <= n-1u_i != v_ip != q1 <= dis_i, limit <= 10^9- At most
10^4calls will be made toquery.
Solution
The main idea of this problem is to create a minimum spanning tree from the edges and the nodes. In the constructor, create a minimum spanning tree using union find and Kruskal’s algorithm. For the method query, the idea is similar to finding the lowest common ancestor.
Java
class DistanceLimitedPathsExist {
int n;
int bits;
UnionFind uf;
int[][] edgeList;
Map<Integer, List<int[]>> mstEdges;
int[][] parent;
int[][] maxWeights;
int[] depths;
boolean[] visited;
public DistanceLimitedPathsExist(int n, int[][] edgeList) {
this.n = n;
this.uf = new UnionFind(n);
this.edgeList = edgeList;
Arrays.sort(this.edgeList, new Comparator<int[]>() {
public int compare(int[] edge1, int[] edge2) {
return edge1[2] - edge2[2];
}
});
mstEdges = new HashMap<Integer, List<int[]>>();
bits = (int) (Math.log(n) / Math.log(2)) + 2;
this.parent = new int[n][bits];
for (int i = 0; i < n; i++)
Arrays.fill(this.parent[i], -1);
this.maxWeights = new int[n][bits];
this.depths = new int[n];
this.visited = new boolean[n];
kruskal();
for (int i = 0; i < n; i++) {
if (!visited[i]) {
depths[i] = 1;
depthFirstSearch(i);
parent[i][0] = i;
}
}
for (int i = 1; i < bits; i++) {
for (int j = 0; j < n; j++) {
parent[j][i] = parent[parent[j][i - 1]][i - 1];
maxWeights[j][i] = Math.max(maxWeights[j][i - 1], maxWeights[parent[j][i - 1]][i - 1]);
}
}
}
public boolean query(int p, int q, int limit) {
if (uf.find(p) != uf.find(q))
return false;
else
return lowestCommonAncestor(p, q) < limit;
}
private void kruskal() {
int edgesCount = edgeList.length;
for (int i = 0; i < edgesCount; i++) {
int[] edge = edgeList[i];
int u = edge[0], v = edge[1], dist = edge[2];
if (uf.union(u, v)) {
List<int[]> list1 = mstEdges.getOrDefault(u, new ArrayList<int[]>());
List<int[]> list2 = mstEdges.getOrDefault(v, new ArrayList<int[]>());
list1.add(new int[]{v, dist});
list2.add(new int[]{u, dist});
mstEdges.put(u, list1);
mstEdges.put(v, list2);
}
}
}
private void depthFirstSearch(int u) {
visited[u] = true;
List<int[]> list = mstEdges.getOrDefault(u, new ArrayList<int[]>());
for (int[] array : list) {
int v = array[0], dist = array[1];
if (!visited[v]) {
depths[v] = depths[u] + 1;
parent[v][0] = u;
maxWeights[v][0] = dist;
depthFirstSearch(v);
}
}
}
private int lowestCommonAncestor(int u, int v) {
if (depths[u] > depths[v]) {
int temp = u;
u = v;
v = temp;
}
int temp = depths[v] - depths[u];
int weight = 0;
int index = 0;
while (temp != 0) {
if (temp % 2 != 0) {
weight = Math.max(weight, maxWeights[v][index]);
v = parent[v][index];
}
temp >>= 1;
index++;
}
if (u == v)
return weight;
for (int i = bits - 1; i >= 0; i--) {
if (parent[u][i] != parent[v][i]) {
weight = Math.max(weight, Math.max(maxWeights[u][i], maxWeights[v][i]));
u = parent[u][i];
v = parent[v][i];
}
}
weight = Math.max(weight, Math.max(maxWeights[u][0], maxWeights[v][0]));
return weight;
}
}
class UnionFind {
int n;
int[] parent;
public UnionFind(int n) {
this.n = n;
this.parent = new int[n];
for (int i = 0; i < n; i++) {
this.parent[i] = i;
}
}
public boolean union(int index1, int index2) {
int ancestor1 = find(index1), ancestor2 = find(index2);
if (ancestor1 == ancestor2)
return false;
else {
parent[find(index2)] = find(index1);
return true;
}
}
public int find(int index) {
if (parent[index] != index)
parent[index] = find(parent[index]);
return parent[index];
}
}
/**
* Your DistanceLimitedPathsExist object will be instantiated and called as such:
* DistanceLimitedPathsExist obj = new DistanceLimitedPathsExist(n, edgeList);
* boolean param_1 = obj.query(p,q,limit);
*/