# 1697. 检查边长度限制的路径是否存在
### 题目地址(1697. 检查边长度限制的路径是否存在)
### 题目描述
```
给你一个 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 <= 105
1 <= edgeList.length, queries.length <= 105
edgeList[i].length == 3
queries[j].length == 3
0 <= ui, vi, pj, qj <= n - 1
ui != vi
pj != qj
1 <= disi, limitj <= 109
两个点之间可能有 多条 边。
```
### 前置知识
* 排序
* [并查集](/leetcode-solution/thinkings/union-find.md)
### 公司
* 暂无
### 思路
本题和 [1170. 比较字符串最小字母出现频次](https://leetcode-cn.com/problems/compare-strings-by-frequency-of-the-smallest-character/) 类似， 都可以采取离线排序优化的方式来解。
具体来说，我们可以分别对 edges 和 queries 进行一次升序排序。接下来，遍历 queries。遍历 queries 的同时**将权值小于 limitj 的边进行合并**。接下来，我们只需要判断 pj 和 qj 是否已经在同一个联通域即可。因此如果 pj 和 qj 在同一个联通域，那么其联通的路径上的所有边必定都小于 limitj，其原因就是前面加粗的那句话。
注意到排序打乱了 queries 的索引，因此我们需要记录一下其原始索引。
做完这道题之后建议大家完成下方的相关题目，以巩固这个知识点。
### 关键点
* 离线查询优化
### 代码
* 语言支持：Python3
Python3 Code:
```python
class UF:
parent = {}
size = {}
cnt = 0
def __init__(self, M):
# 初始化 parent，size 和 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(key=lambda a:a[2])
queries = [(fr, to, w, i) for i, [fr, to, w] in enumerate(queries)]
queries.sort(key=lambda 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
```
**复杂度分析**
令 m, q edges 和 queries 的长度。
* 时间复杂度：$O(mlogm + qlogq)$
* 空间复杂度：$O(n + q)$
### 相关题目
* [1170. 比较字符串最小字母出现频次](https://leetcode-cn.com/problems/compare-strings-by-frequency-of-the-smallest-character/)
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1697.checking-existence-of-edge-length-limited-paths.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.