Welcome to Subscribe On Youtube
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)
Returnstrue
if there exists a path fromp
toq
such 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^4
0 <= edgeList.length <= 10^4
edgeList[i].length == 3
0 <= u_i, v_i, p, q <= n-1
u_i != v_i
p != q
1 <= dis_i, limit <= 10^9
- At most
10^4
calls 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.
-
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); */