第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
1697. 检查边长度限制的路径是否存在
题目地址(1697. 检查边长度限制的路径是否存在)
题目描述
1
给你一个 n 个点组成的无向图边集 edgeList ，其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边。请注意，两个点之间可能有 超过一条边 。
2
3
给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj] ，你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径，且这条路径上的每一条边都 严格小于 limitj 。
4
5
请你返回一个 布尔数组 answer ，其中 answer.length == queries.length ，当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false 。
6
7
8
9
示例 1：
Copied!
1
输入：n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
2
输出：[false,true]
3
解释：上图为给定的输入数据。注意到 0 和 1 之间有两条重边，分别为 2 和 16 。
4
对于第一个查询，0 和 1 之间没有小于 2 的边，所以我们返回 false 。
5
对于第二个查询，有一条路径（0 -> 1 -> 2）两条边都小于 5 ，所以这个查询我们返回 true 。
6
示例 2：
Copied!
1
输入：n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
2
输出：[true,false]
3
解释：上图为给定数据。
4
5
6
提示：
7
8
2 <= n <= 105
9
1 <= edgeList.length, queries.length <= 105
10
edgeList[i].length == 3
11
queries[j].length == 3
12
0 <= ui, vi, pj, qj <= n - 1
13
ui != vi
14
pj != qj
15
1 <= disi, limitj <= 109
16
两个点之间可能有 多条 边。
Copied!
前置知识
- 排序
公司
- 暂无
思路
具体来说，我们可以分别对 edges 和 queries 进行一次升序排序。接下来，遍历 queries。遍历 queries 的同时将权值小于 limitj 的边进行合并。接下来，我们只需要判断 pj 和 qj 是否已经在同一个联通域即可。因此如果 pj 和 qj 在同一个联通域，那么其联通的路径上的所有边必定都小于 limitj，其原因就是前面加粗的那句话。
注意到排序打乱了 queries 的索引，因此我们需要记录一下其原始索引。
做完这道题之后建议大家完成下方的相关题目，以巩固这个知识点。
关键点
- 离线查询优化
代码
- 语言支持：Python3
Python3 Code:
1
class UF:
2
parent = {}
3
size = {}
4
cnt = 0
5
def __init__(self, M):
6
# 初始化 parent，size 和 cnt
7
for i in range(M):
8
self.parent[i] = i
9
self.size[i] = 1
10
11
def find(self, x):
12
while x != self.parent[x]:
13
x = self.parent[x]
14
# 路径压缩
15
self.parent[x] = self.parent[self.parent[x]];
16
return x
17
def union(self, p, q):
18
if self.connected(p, q): return
19
# 小的树挂到大的树上， 使树尽量平衡
20
leader_p = self.find(p)
21
leader_q = self.find(q)
22
if self.size[leader_p] < self.size[leader_q]:
23
self.parent[leader_p] = leader_q
24
self.size[leader_p] += self.size[leader_q]
25
else:
26
self.parent[leader_q] = leader_p
27
self.size[leader_q] += self.size[leader_p]
28
self.cnt -= 1
29
def connected(self, p, q):
30
return self.find(p) == self.find(q)
31
class Solution:
32
def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:
33
m = len(queries)
34
edgeList.sort(key=lambda a:a[2])
35
queries = [(fr, to, w, i) for i, [fr, to, w] in enumerate(queries)]
36
queries.sort(key=lambda a:a[2])
37
ans = [False] * m
38
uf = UF(n)
39
j = 0
40
for fr, to, w, i in queries:
41
while j < len(edgeList) and edgeList[j][2] < w:
42
uf.union(edgeList[j][0], edgeList[j][1])
43
j += 1
44
if uf.connected(fr, to): ans[i] = True
45
return ans
Copied!
复杂度分析
令 m, q edges 和 queries 的长度。
- 时间复杂度：$O(mlogm + qlogq)$
- 空间复杂度：$O(n + q)$
相关题目
最近更新 1yr ago