Leetcode1697-检查边长度限制的路径是否存在

并查集+离线

我们把所有询问按询问的长度限制排序，边集也按边权大小升序排序。离线处理所有询问，依次从限制小的询问来处理，每回答一个询问，我们把边权小于这个限制的边都加入到图中，在这一步用并查集来维护点的连通性；把符合要求的边都加入到图中后，再在并查集中查询询问的两点是否连通即可。

class Solution {
public:
    vector<int> p=vector<int>(100010);
    int findd(int x){
        return p[x]==x?x:p[x]=findd(p[x]);
    }
    void unionn(int x,int y){
        x=findd(x),y=findd(y);
        p[x]=y;
    }
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        int m=queries.size();
        vector<bool> ans(m);
        iota(p.begin(),p.begin()+n,0);
        for(int i=0;i<m;i++) queries[i].push_back(i);
        sort(queries.begin(),queries.end(),[](const auto &a,const auto &b){
            return a[2]<b[2];
        });
        sort(edgeList.begin(),edgeList.end(),[](const auto &a,const auto &b){
            return a[2]<b[2];
        });
        for(int i=0,j=0;i<m;i++){
            while(j<edgeList.size()&&edgeList[j][2]<queries[i][2]){
                unionn(edgeList[j][0],edgeList[j][1]);
                j++;
            }
            int x=findd(queries[i][0]),y=findd(queries[i][1]);
            ans[queries[i][3]]=(x==y);
        }
        return ans;
    }
};

时间复杂度：O（qlogq+mlogm+α(m)），前两个复杂度为排序的复杂度，α(m)为并查集操作的复杂度。

空间复杂度：O（n）。