检查边长度限制的路径是否存在 (并查集,排序，双指针) (LC)_边排序后 并查集

题目地址

按询问的长度从小到大排序，并且按所有边从小到大排序。

对于第一个询问，把所有边长小于询问长度加入到一个集合，最后询问是否在在一个集合。
对于后面的的询问，保持当前已有的集合，继续往里面添加边长小于当前长度的点。

代码：

class Solution {
public:
    struct Node{
        int a,b,c,d;
        bool operator <(const Node&T)const{
            return c < T.c;
        }
    };
    vector<int> fa;
    int find(int x){
        if(x != fa[x]) fa[x] = find(fa[x]);
        return fa[x];
    }
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        int m = (int)edgeList.size(),mm = (int)queries.size();
        Node e[m],q[mm];
        vector<bool> ans(mm);
        fa.resize(n);
        for(int i=0;i<n;i++) fa[i] = i;
        for(int i=0;i<m;i++) e[i] = {edgeList[i][0],edgeList[i][1],edgeList[i][2]};
        for(int i=0;i<mm;i++) q[i] = {queries[i][0],queries[i][1],queries[i][2],i};
        sort(e,e+m);sort(q,q+mm);
        for(int i=0,j=0;i<mm;i++){
            while(j < m && e[j].c < q[i].c){
                int a = find(e[j].a),b = find(e[j].b);
                fa[a] = b;
                j ++;
            }
            ans[q[i].d] = find(q[i].a) == find(q[i].b);
        }
        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