当前位置:   article > 正文

leetcode - 1697 - 检查边长度限制的路径是否存在 - 最小生成树 - 并查集 - 离线算法

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

欢迎关注更多精彩
关注我,学习常用算法与数据结构,一题多解,降维打击。

题目描述

[1697] 检查边长度限制的路径是否存在

  • https://leetcode-cn.com/problems/checking-existence-of-edge-length-limited-paths/

给你一个 n 个点组成的无向图边集 edgeList ,其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边。请注意,两个点之间可能有 超过一条边 。

给你一个查询数组queries ,其中 queries[j] = [pj, qj, limitj] ,你的任务是对于每个查询 queries[j] ,判断是否存在从 pj 到 qj 的路径,且这条路径上的每一条边都 严格小于 limitj 。

请你返回一个 布尔数组 answer ,其中 answer.length == queries.length ,当 queries[j] 的查询结果为 true 时, answer 第 j 个值为 true ,否则为 false 。

示例 1:

输入:n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
输出:[false,true]
解释:上图为给定的输入数据。注意到 0 和 1 之间有两条重边,分别为 2 和 16 。
对于第一个查询,0 和 1 之间没有小于 2 的边,所以我们返回 false 。
对于第二个查询,有一条路径(0 -> 1 -> 2)两条边都小于 5 ,所以这个查询我们返回 true 。
示例 2:

输入:n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
输出:[true,false]
解释:上图为给定数据。

提示:

2 <= n <= 10^5
1 <= edgeList.length, queries.length <= 10^5
edgeList[i].length == 3
queries[j].length == 3
0 <= ui, vi, pj, qj <= n - 1
ui != vi
pj != qj
1 <= disi, limitj <= 10^9
两个点之间可能有 多条 边。

Related Topics
  • 最小生成树
  • 离线查询
  • 并查集
  • bitset

题目剖析&信息挖掘

此题为图论题,需要用到最小生成树,离线算法技巧。

解题思路

  • 先看到题目数据规模,查询和树节点都有10^5,如果每个查询单独查询肯定不行,需要批量查询
  • 感觉可能的方案有离线查询,第一个想到的是如果这是一棵树,可以按照最近公共祖先离线算法,可以做到O(n)复杂度。
  • 那么首先要对整个图进行简化,题目要求的是使2点之间通路上的每条边值越小越好。
  • 也就是说2点之间的最优路径是固定的,我们可以对无用边进行删除,只取有用边。
  • 这里想到了最小生成树方法。
  • 最小生成树方法是保证生成整个数时代价最小,那么能不能保证每2点之间边的最大值最小呢(结论1)。
  • 答案是可以的。
  • 假设图中有a,b 两点,我们想知道一下连接a, b两点路径上最大值最小是多少。
  • 可以将边按小到大排序,然后一条一条加入,每次都加入一条边e都检测a,b连通性。如果连通了,说明当前新加入的边就是路径上最大值最小的边。
  • 证明如下:
  • 反证法,如果e不是路径上最大值的最小值。那么肯定存在一种方案利用所有权值<e的边,使得a,b连通。
  • 在最小生成树的前提下,显然是不可能的。
  • 到了这里突然想到了更简单的方法。(方法一)
  • 方法二 : 先生成最小生成树,再利用公共祖先算法离线查询(待实现)

方法一 最小生成树+离线计算

分析
  • 有了上面的结论1的基础。突然想到了一种边生成树边查找的方法。
  • 结论1可以得到另一个结论:在生成树的过程中,如果长度为l的边都加完了,说明目前图中连通的点的路径上最大值就是l。
  • 我们可以找到查询中limit>l的例子进行连通性测试就可以得到结果。
  • 复杂度分析:每条边遍历一次,每个查询例子查询一次,复杂为O(m+q)
思路
const int N = 1e6 + 10;

/*
并查集,判连通用
*/
class UnionSet{
private:
    int father[N];
    int num;
public:
  	// 初始化
    UnionSet(int n)
    {
    }

  	// 查询父结点
    int Find(int x){
        
    }

  //合并结点
    bool Join(int x, int y)
    {
    }

  //判断结点是否连通
    bool IsLink(int x, int y)
    {
    }
};

bool LessVector(vector<vector<int>>& q1, vector<vector<int>>& q2)
{
    return q1[2]<q2[2];
}


class Solution {
public:
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        // 为querys 加上编号
        for (int i = 0; i < queries.size(); ++i) {
            queries[i].push_back(i);
        }
        sort(edgeList.begin(), edgeList.end(), LessVector);
        sort(queries.begin(), queries.end(), LessVector);
        vector<bool> ans = vector<bool>(queries.size(), false);

        UnionSet us(n+10);

        int curq = 0;
        for (int i = 0; i < edgeList.size(); ++i) {
            us.Join(edgeList[i][0], edgeList[i][1]);

            // 相同的边添加完以后,进行一轮查询,找出limit > 当前边长,且小于等下一轮添加边长的查询。
            if (i==edgeList.size()-1 || edgeList[i+1][2]!=edgeList[i][2])
            {
                int nextWeight = INT32_MAX;
                if(i==edgeList.size()-1) nextWeight = edgeList[i+1][2];
                for (; curq < queries.size() && queries[curq][2]<=nextWeight; ++curq) {
                    if (queries[curq][2]<=edgeList[i][2])continue; // 只查询limit>edgeList[i][2], <=edgeList[i][2] 的在之前已查询过了,或者根本不;连通
                    if(us.IsLink(queries[curq][0], queries[curq][1])) ans[queries[curq][3]] = true;
                }
            }
        }

        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
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
注意
  • 查询要按照limit进行排序
  • 查询要等同样边长都加完再进行
知识点
  • 最小生成树
  • 离线查询
  • 并查集
复杂度
  • 时间复杂度:O(m+q)
  • 空间复杂度:O(n+m+q)
参考
代码实现
const int N = 1e6 + 10;

/*
并查集,判连通用
*/
class UnionSet{
private:
    int father[N];
    int num;
public:

    // 初始化
    UnionSet(int n)
    {
        num = n;
        for (int i = 0; i < n; ++i) {
            father[i]=i;
        }
    }

    // 查询父结点
    int Find(int x){
        int s = x;
        while(father[x]!=x)x=father[x];

        /*
         * 缩短路径优化
         */

        while(s!=father[s])
        {
            int temp = father[s];
            father[s]=x;
            s = temp;
        }

        return x;
    }

    //合并结点
    bool Join(int x, int y)
    {
        x = Find(x);
        y = Find(y);
        if (x==y)return false;
        father[x]=y;
        return true;
    }

    //判断结点是否连通
    bool IsLink(int x, int y)
    {
        x = Find(x);
        y = Find(y);
        return x==y;
    }
};

bool LessVector(vector<vector<int>>& q1, vector<vector<int>>& q2)
{
    return q1[2]<q2[2];
}


class Solution {
public:
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        // 为querys 加上编号
        for (int i = 0; i < queries.size(); ++i) {
            queries[i].push_back(i);
        }
        sort(edgeList.begin(), edgeList.end(), LessVector);
        sort(queries.begin(), queries.end(), LessVector);
        vector<bool> ans = vector<bool>(queries.size(), false);

        UnionSet us(n+10);

        int curq = 0;
        for (int i = 0; i < edgeList.size(); ++i) {
            us.Join(edgeList[i][0], edgeList[i][1]);

            // 相同的边添加完以后,进行一轮查询,找出limit > 当前边长,且小于等下一轮添加边长的查询。
            if (i==edgeList.size()-1 || edgeList[i+1][2]!=edgeList[i][2])
            {
                int nextWeight = INT32_MAX;
                if(i==edgeList.size()-1) nextWeight = edgeList[i+1][2];
                for (; curq < queries.size() && queries[curq][2]<=nextWeight; ++curq) {
                    if (queries[curq][2]<=edgeList[i][2])continue; // 只查询limit>edgeList[i][2], <=edgeList[i][2] 的在之前已查询过了,或者根本不;连通
                    if(us.IsLink(queries[curq][0], queries[curq][1])) ans[queries[curq][3]] = true;
                }
            }
        }

        return ans;
    }
};
/*
5
[[0,1,10],[1,2,5],[2,3,9],[3,4,13]]
[[0,4,14],[1,4,13]]
5
[[0,1,10],[1,2,10],[2,3,10],[3,4,10]]
[[0,4,11],[1,4,11],[0,4,10],[1,4,10]]
5
[[0,1,10],[1,2,10],[2,3,9],[3,4,9]]
[[0,4,11],[1,4,11],[0,4,10],[1,4,10]]
*/

  • 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
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108

相关题目

https://ac.nowcoder.com/acm/contest/9700/D 可以利用最小生成树思想


本人码农,希望通过自己的分享,让大家更容易学懂计算机知识。

在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/131036
推荐阅读
相关标签
  

闽ICP备14008679号