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) 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.

Example 1:

Image text

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 to query.

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);
     */
    
  • Todo
    
  • print("Todo!")
    

All Problems

All Solutions