跳转至

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
  • 两个点之间可能有 多条 边。

解题思路#

edgeList 按边权从小到大排序，queries 按 limit 从小到大排序。

每次将小于 queries[i] 中的边加入到并查集中，然后判断查询点是否连通。

 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
class Solution:
    def distanceLimitedPathsExist(
        self, n: int, edgeList: List[List[int]], queries: List[List[int]]
    ) -> List[bool]:
        fa = list(range(n))
        size = [1] * n

        def find(x):
            if x != fa[x]:
                fa[x] = find(fa[x])
            return fa[x]

        def union(x, y):
            x, y = find(x), find(y)
            if x == y:
                return
            if size[x] < size[y]:
                x, y = y, x
            fa[y] = x
            size[x] += size[y]

        e = sorted(range(len(edgeList)), key=lambda i: edgeList[i][-1])
        q = sorted(range(len(queries)), key=lambda i: queries[i][-1])

        ans = [True] * len(q)
        j = 0
        for i in q:
            x, y, l = queries[i]
            while j < len(e) and edgeList[e[j]][-1] < l:
                union(edgeList[e[j]][0], edgeList[e[j]][1])
                j += 1

            if find(x) != find(y):
                ans[i] = False
        return ans
返回顶部

在手机上阅读