LeetCode 1697. 检查边长度限制的路径是否存在(排序+并查集)
发布日期:2021-07-01 03:35:05
浏览次数:2
分类:技术文章
本文共 2326 字,大约阅读时间需要 7 分钟。
文章目录
1. 题目
给你一个 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^51 <= edgeList.length, queries.length <= 10^5edgeList[i].length == 3queries[j].length == 30 <= ui, vi, pj, qj <= n - 1ui != vipj != qj1 <= disi, limitj <= 10^9两个点之间可能有 多条 边。
来源:力扣(LeetCode)
链接: 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
相关题目: (字符串合并)- limits 短的优先查询,边也排序,满足要求的在并查集中合并两点
class dsu{ //并查集public: vector f; dsu(int n) { f.resize(n); for(int i = 0; i < n; ++i) f[i] = i; } void merge(int a, int b) { int fa = find(a), fb = find(b); f[fa] = fb; } int find(int a) { if(a == f[a]) return a; return f[a] = find(f[a]); }};class Solution { public: vectordistanceLimitedPathsExist(int n, vector >& edgeList, vector >& queries) { dsu u(n); vector ans(queries.size(), false); vector q_id(queries.size()); iota(q_id.begin(), q_id.end(), 0); //生成 0,1,2,3... sort(q_id.begin(), q_id.end(),[&](auto& a, auto& b){ return queries[a][2] < queries[b][2];//对查询的id排序,距离小的先查询 }); sort(edgeList.begin(), edgeList.end(),[&](auto& a, auto& b){ return a[2] < b[2];//边短的先加入并查集合并 }); int j = 0, limit; for(int i = 0; i < q_id.size(); ++i) { limit = queries[q_id[i]][2]; while(j < edgeList.size() && edgeList[j][2] < limit)//距离满足要求 { u.merge(edgeList[j][0], edgeList[j][1]);//合并两点 j++; } if(u.find(queries[q_id[i]][0]) == u.find(queries[q_id[i]][1])) ans[q_id[i]] = true; } return ans; }};
我的CSDN
长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!
转载地址:https://michael.blog.csdn.net/article/details/111462665 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
感谢大佬
[***.8.128.20]2024年04月09日 04时10分40秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
深入理解python--线程、进程与协程(1)
2019-05-01
Java--流重点总结初稿
2019-05-01
Html2Servlet--Html代码转换为Servlet小程序
2019-05-01
HTTP认证方式
2019-05-01
图书商城:分类模块
2019-05-01
图书商城:订单模块
2019-05-01
开源全能播放器Vitamio的使用
2019-05-01
使用ViewPager加载页面出现空白
2019-05-01
ImageView scaleType
2019-05-01
RecyclerView notifyItem闪屏问题
2019-05-01
dubbo学习笔记 十一 dubbo-rpc之模块
2019-05-01
motan学习笔记 五 opentracing学习入门
2019-05-01
求列表最长子序列
2019-05-01
字符串的排序
2019-05-01
内存分配(mallloc,calloc,realloc,new)
2019-05-01
ffmpeg & mplayer & vlc 手册
2019-05-01
Go语言并发组件
2019-05-01
简析STUN协议
2019-05-01
使用 Minidumps 和 Visual Studio .NET 进行崩溃后调试
2019-05-01