1697. Checking Existence of Edge Length Limited Paths

Question

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.

Given an array queries, where queries[j] = [pj, qj, limitj], your task is to determine for each queries[j] whether there is a path between pj and qj such that each edge on the path has a distance strictly less than limitj .

Return a boolean array answer, where answer.length == queries.length and the jth value of answer is true if there is a path for queries[j] is true, and false otherwise.

Solution

As we only care about the distance between any two nodes,
we can disregard it if the distance between two nodes is less than limit and using Union-Find to connect the nodes.

Initially, we sort both the edgeList and queries based on their distance and limit.
Starting from the minimum limit, we traverse each edge from by ascending order.
If the distance between two nodes is strictly less than limit, we combine them in the Union-Find.
If the distance is greater than limit, we check whether the two nodes are connected and save the boolean value to ans.
We then move on to the next query and repeat the process.

由于只关注每条边的distance，因此如果两个节点满足条件，则我们可以忽视其中的距离，因此我们可以使用并查集合并节点们。

先排序edgeList及queries。
从最小的limit开始，遍历每条边，当边的distance严格小于limit时，将两个节点添加到并查集。
当边等于或大于limit，则查询当前query的两个节点是否联通，并保存真值到ans。
然后查询下一个query的limit。

Code

class Solution {
    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
        boolean[] ans = new boolean[queries.length];
        for(int i = 0; i < queries.length; i++){
            queries[i] = new int[]{queries[i][0], queries[i][1], queries[i][2], i};
        }
        Arrays.sort(edgeList, (a, b) -> Integer.compare(a[2], b[2]));
        Arrays.sort(queries, (a, b) -> Integer.compare(a[2], b[2]));
        // sort two arrays with limit and weight

        UnionFind uf = new UnionFind(n);
        int i = 0;
        for(int[] q : queries){
            int u = q[0], v = q[1], limit = q[2], id = q[3];
            while(i < edgeList.length && edgeList[i][2] < limit){
                uf.union(edgeList[i][0], edgeList[i][1]);
                // connect two nodes if edge's weight less than limit
                i++;
            }
            ans[id] = uf.isConnected(u, v);
        }
        return ans;
    }
}

class UnionFind {
    public int[] parent;
    public int[] rank;
    UnionFind(int n){
        parent = new int[n];
        rank = new int[n];
        for(int i = 0; i < n; i++){
            parent[i] = i;
            rank[i] = 0;
       }
    }
    public int find(int i) {
        if(parent[i] == i) return i;
        parent[i] = find(parent[i]);
        return parent[i];
    }

    public void union(int a, int b) {
        int pa = find(a), pb = find(b);
        if(rank[pa] < rank[pb]) {
            parent[pa] = pb;
        }
        else if(rank[pa] > rank[pb]){
            parent[pb] = pa;
        }
        else{
            parent[pb] = pa; 
            rank[pa]++;
        }
    }

    public boolean isConnected(int a, int b){
        return find(a) == find(b);
    }
}