Skip to content

Latest commit

 

History

History
140 lines (103 loc) · 4.68 KB

1697.checking-existence-of-edge-length-limited-paths.md

File metadata and controls

140 lines (103 loc) · 4.68 KB

题目地址(1697. 检查边长度限制的路径是否存在)

https://leetcode-cn.com/problems/checking-existence-of-edge-length-limited-paths/

题目描述

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

前置知识

公司

  • 暂无

思路

本题和 1170. 比较字符串最小字母出现频次 类似, 都可以采取离线排序优化的方式来解。

具体来说,我们可以分别对 edges 和 queries 进行一次升序排序。接下来,遍历 queries。遍历 queries 的同时将权值小于 limitj 的边进行合并。接下来,我们只需要判断 pj 和 qj 是否已经在同一个联通域即可。因此如果 pj 和 qj 在同一个联通域,那么其联通的路径上的所有边必定都小于 limitj,其原因就是前面加粗的那句话。

注意到排序打乱了 queries 的索引,因此我们需要记录一下其原始索引。

做完这道题之后建议大家完成下方的相关题目,以巩固这个知识点。

关键点

  • 离线查询优化

代码

  • 语言支持:Python3

Python3 Code:

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)$

相关题目