力扣(LeetCode)1697. 检查边长度限制的路径是否存在(C++)_力扣 两点之间连通增加的最小边长度

并查集+离线查询

由于评测系统对 $vector$ 的排序可能较慢，使用结构体保存 $vector$ ，接下来的查询和边集就对结构体操作。

结构体的属性 $a$ 点 、 $b$ 点 、$c$ 长度、 $d$ 顺序。重载 $<$ ，排序时按照 $c$ 长度升序。

初始化并查集，然后处理查询。

由于边集和查询都按照长度升序，从左往右，依次遍历查询和长度，维护并查集，将长度小于查询的边插入并查集。维护完并查集之后，利用并查集 $O(1)$ 至 $O(logn)$ 时间判断两点之间的连通性，维护答案，即为所求。

const int N = 100010;
struct Node{
    int a,b,c,d;
    bool operator < (const Node &t){
        return c<t.c;
    }
}e[N],q[N];
class Solution {
public:
    vector<int> p;
    int find(int x){
        if(p[x]!=x) p[x] = find(p[x]);
        return p[x];
    }
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& ee, vector<vector<int>>& qq) {
        int m = ee.size(), k = qq.size();
        for(int i= 0 ;i<m;i++)
            e[i] = {ee[i][0],ee[i][1],ee[i][2]};
        for(int i = 0;i<k;i++)
            q[i] = {qq[i][0],qq[i][1],qq[i][2],i};
        sort(e,e+m),sort(q,q+k);
        p = vector<int>(n,0);
        for(int i = 0;i<n;i++) p[i] = i;
        vector<bool>ans(k,0);
        for(int i = 0,j=0;i<k;i++){
            while(j<m&&e[j].c<q[i].c){
                int a = e[j].a, b = e[j].b;
                p[find(a)] = find(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
34
35

1. 时间复杂度 : $O(nlogn)$ ， 变量过多，用无实义的 $n$ 代指所有变量，整体时间复杂度是 $O(nlogn)$ 级别，感兴趣的读者可以自行分析 。
2. 空间复杂度 : $O(m+k+n)$ ， 边的数量 $m$ ，查询的数量 $k$ ，点的数量 $n$ ，并查集的空间复杂度 $O(n)$ ，额外保存边集和查询的空间复杂度 $O(m+k)$ ，总体空间复杂度 $O(m+k+n)$ 。

AC

致语

• 理解思路很重要
• 读者有问题请留言，清墨看到就会回复的。