LeetCode 1697 检查边长度限制的路径是否存在离线查询 并查集的带权图连通性判定【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文以 problems/1697.checking-existence-of-edge-length-limited-paths.md 为核心系统讲解 LeetCode 1697「检查边长度限制的路径是否存在」一题。题目要求在带权无向图中对大量两点之间是否存在全边严格小于某阈值 limit 的路径的查询给出布尔回答本仓库给出的解法将边与查询分别按权值/阈值升序排序配合并查集增量合并把每次查询压到接近 O(1)整体复杂度 O(m log m q log q)。读完本文你将掌握离线排序 并查集这一处理大规模带权连通性查询的通用套路并能在 thinkings/union-find.md 提供的并查集模板之上自如改造如本题的增量合并、problems/3108.minimum-cost-walk-in-weighted-graph.md 的带权合并。题目背景与问题定义给定一个 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查询成立时对应位置为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两条边的长度 2 和 4 都小于 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]解释查询[0,4,14]存在全边小于 14 的路径而查询[1,4,13]中边[3,4]长度为 13要求严格小于 13因此不成立。数据范围约束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两个点之间可能有多条边n、m、q 均达到 10^5 量级且边权可达 10^9说明任何 O(n·q) 级别的朴素逐查询遍历算法都无法通过必须引入全局优化。前置知识排序sort作为离线优化的基础工具并查集Union-Find / Disjoint Set用于维护动态联通性其原理与模板见本仓库 thinkings/union-find.md。核心思路离线查询优化朴素的痛点若对每个查询单独处理要么对每个查询在图上做一次 BFS/DFS 并剪掉权值 ≥ limit 的边要么对每个查询跑一次 Kruskal 式的最小生成树判断。最坏情况下复杂度为 O(q × (m n))在 10^5 量级下完全不可行。关键观察查询与边的单调性本题存在一个非常强的单调结构随着 limit 增大可用的边只会越来越多两点之间的联通关系只会从不联通变为联通且一旦联通就永久联通。原因在于若把边权严格小于 limit作为过滤条件那么 limit 越大被允许的边集合越大联通关系对边集合是单调的边越多联通性只会增强不会回退。原文档指出本题与 1170「比较字符串最小字母出现频次」类似都可以采取离线排序优化的方式求解——先处理小 limit 的查询再处理大 limit 的查询每个查询可复用于之前已合并的边避免重复建图。算法流程对边排序将edgeList按边权disi升序排序对查询排序为每个查询保留原始下标将queries按limitj升序排序因为排序会打乱查询的原始索引必须先记录其原始下标增量合并用一个指针j遍历边数组对于当前查询(fr, to, w, i)只要edgeList[j][2] w就把这条边的两个端点union起来指针右移回答查询合并完所有小于w的边后若uf.connected(fr, to)为真则该查询答案为true否则为false。为什么两点联通 ⇒ 路径上所有边都严格小于 limit这正是增量合并的保证当前查询所合并的每一条边其权值都在该查询的 limit 之下因此联通路径上的全部边必然严格小于 limit。反之如果两点不联通说明所有可用的小于 limit 的边都不足以把它们连起来路径自然不存在。由于每个查询依赖的是所有边权 limit 的边而查询按 limit 升序处理边指针只会单调前进、每条边最多被合并一次整体摊还代价极低。代码实现Python3以下代码取自原文档UF类对应仓库 thinkings/union-find.md 中的不带权并查集模板class UF: parent {} size {} cnt 0 def __init__(self, M): # 初始化 parentsize 和 cnt for i in range(M): self.parent[i] i self.size[i] 1 def find(self, x): while x ! self.parent[x]: x self.parent[x] # 路径压缩 self.parent[x] self.parent[self.parent[x]]; return x def union(self, p, q): if self.connected(p, q): return # 小的树挂到大的树上 使树尽量平衡 leader_p self.find(p) leader_q self.find(q) if self.size[leader_p] self.size[leader_q]: self.parent[leader_p] leader_q self.size[leader_p] self.size[leader_q] else: self.parent[leader_q] leader_p self.size[leader_q] self.size[leader_p] self.cnt - 1 def connected(self, p, q): return self.find(p) self.find(q) class Solution: def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) - List[bool]: m len(queries) edgeList.sort(keylambda a:a[2]) queries [(fr, to, w, i) for i, [fr, to, w] in enumerate(queries)] queries.sort(keylambda a:a[2]) ans [False] * m uf UF(n) j 0 for fr, to, w, i in queries: while j len(edgeList) and edgeList[j][2] w: uf.union(edgeList[j][0], edgeList[j][1]) j 1 if uf.connected(fr, to): ans[i] True return ans代码要点逐行解读edgeList.sort(keylambda a:a[2])按边权升序为单调指针j的推进打基础queries [(fr, to, w, i) for i, [fr, to, w] in enumerate(queries)]把原始索引 i 存入元组这是离线排序后能正确回填答案位置的关键queries.sort(keylambda a:a[2])按 limit 升序保证单调性while j len(edgeList) and edgeList[j][2] w注意是严格小于而非与题目严格小于 limit的定义严格对齐——当边权恰好等于 limit 时不允许通过if uf.connected(fr, to): ans[i] True按原始索引i回填未联通的位置保持初始值False。关于 UF 模板的两点说明原文档示例代码中union的size更新方式self.size[leader_p] self.size[leader_q]与本仓库模板thinkings/union-find.md中更新根节点size[leader_q] size[leader_p]略有差异属于按秩合并的实现细节差异不影响正确性——只要保证把小树挂到大树且父节点一侧的 size 被正确累加即可题目数据保证无向图中点、边均为 10^5 量级find使用路径压缩、union使用按秩合并后摊还复杂度趋近 O(1)严格来说是阿克曼函数反函数的量级这是整体算法高效的根本保证。复杂度分析令 m 为edgeList的长度q 为queries的长度。时间复杂度$O(mlogm qlogq)$。主要开销来自两次排序排序后的扫描过程中每条边至多被合并一次每次 find/union 摊还接近 O(1)空间复杂度$O(n q)$。UF需要存储 n 个点的 parent/sizeO(n)同时为保留查询原始索引需要构造长度为 q 的元组数组O(q)答案数组本身也占用 O(q)合并记为 $O(n q)$。对比朴素做法每查询一次 DFS/BFSO(q(m n))离线优化将复杂度从乘积级降为排序级正是本题 10^5 数据规模下可行的关键。并查集原理速览本题的核心数据结构是并查集仓库 thinkings/union-find.md 中有完整原理讲解这里提炼与本解题密相关的三点find找到集合代表find(x)返回 x 所属集合的代表根节点。通过路径压缩self.parent[x] self.parent[self.parent[x]]每次查找后把树高显著压低避免 find 退化为 O(n)。union合并两个集合union(p, q)先找两个根再按秩size合并把较小的树挂到较大的树上保持树尽量平衡——即按秩合并。connected判定联通性connected(p, q)等价于find(p) find(q)这正是本题对每个查询的回答逻辑。同类题拓展离线并查集的更多应用掌握离线排序 并查集套路后可以继续挑战本仓库中相关题目以巩固problems/1631.path-with-minimum-effort.md二维网格上的最小体力消耗路径同样基于阈值越大越容易联通的单调性可二分答案或按边权排序增量合并problems/1970.last-day-where-you-can-still-cross.md矩阵被水淹没的最后一天逆向思考即随时间增加联通性增强配合二分/并查集求解该题题解中即点名与 1631 相似problems/3108.minimum-cost-walk-in-weighted-graph.md带权图里旅途的最小代价在并查集基础上维护联通块内所有边权的按位与是带权并查集的典型变体其union需要同步更新all_and值thinkings/union-find.md 的练习清单还列有 547朋友圈、721账户合并、990等式方程的可满足性等连通性题目均在并查集模板上套用即可。总结LeetCode 1697 的核心收获有二离线查询优化当查询之间共享可复用的中间状态、且状态随某个参数limit单调变化时按该参数排序后增量构建答案可将大量重复计算摊平成一次线性扫描并查集的连通性判定用边权严格小于 limit 才合并的增量式并查集把路径上每条边都小于 limit的判定转化为两点是否联通一次 find 即得答案。做题时需特别注意严格小于的边界处理而非以及排序后通过元组保留查询原始下标以保证答案回填正确。建议将 thinkings/union-find.md 的并查集模板作为标准件反复使用并完成上述拓展题目即可把该套路内化为自己的解题武器库。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 1697 检查边长度限制的路径是否存在：离线查询 + 并查集的带权图连通性判定
LeetCode 1697 检查边长度限制的路径是否存在离线查询 并查集的带权图连通性判定【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文以 problems/1697.checking-existence-of-edge-length-limited-paths.md 为核心系统讲解 LeetCode 1697「检查边长度限制的路径是否存在」一题。题目要求在带权无向图中对大量两点之间是否存在全边严格小于某阈值 limit 的路径的查询给出布尔回答本仓库给出的解法将边与查询分别按权值/阈值升序排序配合并查集增量合并把每次查询压到接近 O(1)整体复杂度 O(m log m q log q)。读完本文你将掌握离线排序 并查集这一处理大规模带权连通性查询的通用套路并能在 thinkings/union-find.md 提供的并查集模板之上自如改造如本题的增量合并、problems/3108.minimum-cost-walk-in-weighted-graph.md 的带权合并。题目背景与问题定义给定一个 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查询成立时对应位置为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两条边的长度 2 和 4 都小于 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]解释查询[0,4,14]存在全边小于 14 的路径而查询[1,4,13]中边[3,4]长度为 13要求严格小于 13因此不成立。数据范围约束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两个点之间可能有多条边n、m、q 均达到 10^5 量级且边权可达 10^9说明任何 O(n·q) 级别的朴素逐查询遍历算法都无法通过必须引入全局优化。前置知识排序sort作为离线优化的基础工具并查集Union-Find / Disjoint Set用于维护动态联通性其原理与模板见本仓库 thinkings/union-find.md。核心思路离线查询优化朴素的痛点若对每个查询单独处理要么对每个查询在图上做一次 BFS/DFS 并剪掉权值 ≥ limit 的边要么对每个查询跑一次 Kruskal 式的最小生成树判断。最坏情况下复杂度为 O(q × (m n))在 10^5 量级下完全不可行。关键观察查询与边的单调性本题存在一个非常强的单调结构随着 limit 增大可用的边只会越来越多两点之间的联通关系只会从不联通变为联通且一旦联通就永久联通。原因在于若把边权严格小于 limit作为过滤条件那么 limit 越大被允许的边集合越大联通关系对边集合是单调的边越多联通性只会增强不会回退。原文档指出本题与 1170「比较字符串最小字母出现频次」类似都可以采取离线排序优化的方式求解——先处理小 limit 的查询再处理大 limit 的查询每个查询可复用于之前已合并的边避免重复建图。算法流程对边排序将edgeList按边权disi升序排序对查询排序为每个查询保留原始下标将queries按limitj升序排序因为排序会打乱查询的原始索引必须先记录其原始下标增量合并用一个指针j遍历边数组对于当前查询(fr, to, w, i)只要edgeList[j][2] w就把这条边的两个端点union起来指针右移回答查询合并完所有小于w的边后若uf.connected(fr, to)为真则该查询答案为true否则为false。为什么两点联通 ⇒ 路径上所有边都严格小于 limit这正是增量合并的保证当前查询所合并的每一条边其权值都在该查询的 limit 之下因此联通路径上的全部边必然严格小于 limit。反之如果两点不联通说明所有可用的小于 limit 的边都不足以把它们连起来路径自然不存在。由于每个查询依赖的是所有边权 limit 的边而查询按 limit 升序处理边指针只会单调前进、每条边最多被合并一次整体摊还代价极低。代码实现Python3以下代码取自原文档UF类对应仓库 thinkings/union-find.md 中的不带权并查集模板class UF: parent {} size {} cnt 0 def __init__(self, M): # 初始化 parentsize 和 cnt for i in range(M): self.parent[i] i self.size[i] 1 def find(self, x): while x ! self.parent[x]: x self.parent[x] # 路径压缩 self.parent[x] self.parent[self.parent[x]]; return x def union(self, p, q): if self.connected(p, q): return # 小的树挂到大的树上 使树尽量平衡 leader_p self.find(p) leader_q self.find(q) if self.size[leader_p] self.size[leader_q]: self.parent[leader_p] leader_q self.size[leader_p] self.size[leader_q] else: self.parent[leader_q] leader_p self.size[leader_q] self.size[leader_p] self.cnt - 1 def connected(self, p, q): return self.find(p) self.find(q) class Solution: def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) - List[bool]: m len(queries) edgeList.sort(keylambda a:a[2]) queries [(fr, to, w, i) for i, [fr, to, w] in enumerate(queries)] queries.sort(keylambda a:a[2]) ans [False] * m uf UF(n) j 0 for fr, to, w, i in queries: while j len(edgeList) and edgeList[j][2] w: uf.union(edgeList[j][0], edgeList[j][1]) j 1 if uf.connected(fr, to): ans[i] True return ans代码要点逐行解读edgeList.sort(keylambda a:a[2])按边权升序为单调指针j的推进打基础queries [(fr, to, w, i) for i, [fr, to, w] in enumerate(queries)]把原始索引 i 存入元组这是离线排序后能正确回填答案位置的关键queries.sort(keylambda a:a[2])按 limit 升序保证单调性while j len(edgeList) and edgeList[j][2] w注意是严格小于而非与题目严格小于 limit的定义严格对齐——当边权恰好等于 limit 时不允许通过if uf.connected(fr, to): ans[i] True按原始索引i回填未联通的位置保持初始值False。关于 UF 模板的两点说明原文档示例代码中union的size更新方式self.size[leader_p] self.size[leader_q]与本仓库模板thinkings/union-find.md中更新根节点size[leader_q] size[leader_p]略有差异属于按秩合并的实现细节差异不影响正确性——只要保证把小树挂到大树且父节点一侧的 size 被正确累加即可题目数据保证无向图中点、边均为 10^5 量级find使用路径压缩、union使用按秩合并后摊还复杂度趋近 O(1)严格来说是阿克曼函数反函数的量级这是整体算法高效的根本保证。复杂度分析令 m 为edgeList的长度q 为queries的长度。时间复杂度$O(mlogm qlogq)$。主要开销来自两次排序排序后的扫描过程中每条边至多被合并一次每次 find/union 摊还接近 O(1)空间复杂度$O(n q)$。UF需要存储 n 个点的 parent/sizeO(n)同时为保留查询原始索引需要构造长度为 q 的元组数组O(q)答案数组本身也占用 O(q)合并记为 $O(n q)$。对比朴素做法每查询一次 DFS/BFSO(q(m n))离线优化将复杂度从乘积级降为排序级正是本题 10^5 数据规模下可行的关键。并查集原理速览本题的核心数据结构是并查集仓库 thinkings/union-find.md 中有完整原理讲解这里提炼与本解题密相关的三点find找到集合代表find(x)返回 x 所属集合的代表根节点。通过路径压缩self.parent[x] self.parent[self.parent[x]]每次查找后把树高显著压低避免 find 退化为 O(n)。union合并两个集合union(p, q)先找两个根再按秩size合并把较小的树挂到较大的树上保持树尽量平衡——即按秩合并。connected判定联通性connected(p, q)等价于find(p) find(q)这正是本题对每个查询的回答逻辑。同类题拓展离线并查集的更多应用掌握离线排序 并查集套路后可以继续挑战本仓库中相关题目以巩固problems/1631.path-with-minimum-effort.md二维网格上的最小体力消耗路径同样基于阈值越大越容易联通的单调性可二分答案或按边权排序增量合并problems/1970.last-day-where-you-can-still-cross.md矩阵被水淹没的最后一天逆向思考即随时间增加联通性增强配合二分/并查集求解该题题解中即点名与 1631 相似problems/3108.minimum-cost-walk-in-weighted-graph.md带权图里旅途的最小代价在并查集基础上维护联通块内所有边权的按位与是带权并查集的典型变体其union需要同步更新all_and值thinkings/union-find.md 的练习清单还列有 547朋友圈、721账户合并、990等式方程的可满足性等连通性题目均在并查集模板上套用即可。总结LeetCode 1697 的核心收获有二离线查询优化当查询之间共享可复用的中间状态、且状态随某个参数limit单调变化时按该参数排序后增量构建答案可将大量重复计算摊平成一次线性扫描并查集的连通性判定用边权严格小于 limit 才合并的增量式并查集把路径上每条边都小于 limit的判定转化为两点是否联通一次 find 即得答案。做题时需特别注意严格小于的边界处理而非以及排序后通过元组保留查询原始下标以保证答案回填正确。建议将 thinkings/union-find.md 的并查集模板作为标准件反复使用并完成上述拓展题目即可把该套路内化为自己的解题武器库。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
