5632. 检查边长度限制的路径是否存在(排序&并查集)_检查边长度的路径是否存在

5632. 检查边长度限制的路径是否存在(排序&并查集)

思路：

1.离线排序+并查集。

将边和询问按权值从小到大排序。
加入所有$w<limit$的边
每次就$find$查找是否连通即可。

时间复杂度：$O(q+mlogn)$

const int N=1e5+5;
struct edge{
    int u,v,d,id;
    bool operator<(const edge&ed)const{
        return d<ed.d;
    }
}e[N],q[N];
vector<int>s;
 int find(int x){
            return x==s[x]?x:s[x]=find(s[x]);
        }
class Solution {
public:
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& E, vector<vector<int>>& Q) {
        int m=E.size(),k=Q.size();
        s.resize(n);
        for(int i=0;i<m;i++){
            e[i]={E[i][0],E[i][1],E[i][2]};
        }
        for(int i=0;i<k;i++)
            q[i]={Q[i][0],Q[i][1],Q[i][2],i};
        sort(e,e+m);
        sort(q,q+k);
        for(int i=0;i<n;i++) s[i]=i;
        vector<bool>ans(k);
        for(int i=0,j=0;i<k;i++){
            while(j<m&&e[j].d<q[i].d){
                int u=e[j].u,v=e[j].v;
                u=find(u),v=find(v);
                if(u!=v) s[u]=v;
                j++;
            }
            ans[q[i].id]=find(q[i].u)==find(q[i].v);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

2.$MST$+倍增$LCA$。

维护一个路径最大数组，题解区有人写了，我就不写了，$justmark$下。