# 1697. Checking Existence of Edge Length Limited Paths
###### tags: `Leetcode` `Hard` `Union Find`
Link: https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/description/
## 思路
我们考虑一下如果只有一个query的话我们会怎么做？显然，我们只要考虑所有权重小于limit的那些edges，看看这些edges能否把query的两个node连接在一起。这是一个典型的Union Find的解法，时间复杂度近似为O(E).

但是本题有多个queries，如果对于每个query都独立解决的话，时间复杂度大致是O(QE)，这样来看是会TLE的。

解决方案很简单。我们优先解决limit低的query，因为它所能用到的edge数目更少，我们只需要查看少量的edges看它是否能够成query两点的连通图。然后我们再解决limit较高的query，此时只需要在已经构建的图里面再添加若干个新edge即可（因为放宽了对权重的要求），再判断query的两点是否联通...可见，如果我们将所有的queries按照limit从小到大排列进行处理，那么相应地我们只需要按照权重从小到大地添加边就行了。在构建联通图的过程中，每条边只需要处理一遍。
## Code

class Solution {
    int[] fa;
    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {      
        for(int i=0; i<queries.length; i++){
            int[] query = queries[i];
            queries[i] = new int[]{query[0], query[1], query[2], i};
        }
        Arrays.sort(edgeList, (a,b)->(a[2]-b[2]));
        Arrays.sort(queries, (a,b)->(a[2]-b[2]));
        boolean[] ans = new boolean[queries.length];
        int idx = 0;
        fa = new int[n];
        for(int i=0; i<n; i++) fa[i] = i;
        for(int i=0; i<queries.length; i++){
            int[] query = queries[i];
            while(idx<edgeList.length && edgeList[idx][2]<query[2]){
                int[] edge = edgeList[idx];
                combine(edge[0], edge[1]);
                idx++;
            }
            ans[query[3]] = find(query[0])==find(query[1]);
        }
        return ans;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        return fa[a] = find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a!=b) fa[a] = b;
    }
}