5632. 检查边长度限制的路径是否存在（图论：并查集）

5632. 检查边长度限制的路径是否存在

排序+并查集

把边从小到大排序
queries询问的边从小到大排序
这样每次只有在每次询问的时候加边，这样加边只加了一次。

class Solution {
public:
    vector<int>p;

    int find(int x){
        if(p[x]!=x)p[x]=find(p[x]);
        return p[x];
    }

    void merge(int a,int b){
        int ra=find(a),rb=find(b);
        p[ra]=rb;
    }

    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& es, vector<vector<int>>& qs) {
        p.resize(n);
        for(int i=0;i<n;i++)p[i]=i;
        for(int i=0;i<qs.size();i++){
            qs[i].push_back(i);
        }
        sort(es.begin(),es.end(),[](const vector<int>&a,const vector<int>&b){
            return a[2]<b[2];
        });
        sort(qs.begin(),qs.end(),[](const vector<int>&a,const vector<int>&b){
            return a[2]<b[2];
        });
        vector<bool>res(qs.size());

        int pos=0;
        for(int i=0;i<qs.size();i++){
            while(pos<es.size() && es[pos][2]<qs[i][2]){
                int a=es[pos][0],b=es[pos][1];
                merge(a,b);
                pos++;
            }
            int ra=find(qs[i][0]),rb=find(qs[i][1]);
            res[qs[i][3]]=ra==rb;
        }
        return res;
    }
};