检查边长度限制的路径是否存在_edgelist = e[0:3]

检查边长度限制的路径是否存在

给你一个 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]

示例 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]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths

代码区

class Solution:
    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:
        edgeList.sort(key=lambda e: e[2])

        # 并查集模板
        fa = list(range(n))
        def find(x: int) -> int:
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x]
        def merge(from_: int, to: int) -> None:
            fa[find(from_)] = find(to)

        answer, k = [False] * len(queries), 0
        # 查询的下标按照 limit 从小到大排序，方便离线
        for i, (p, q, limit) in sorted(enumerate(queries), key=lambda p: p[1][2]):
            while k < len(edgeList) and edgeList[k][2] < limit:
                merge(edgeList[k][0], edgeList[k][1])
                k += 1
            answer[i] = find(p) == find(q)
        return answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

解析

分析一下该题目：对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径，且这条路径上的每一条边都 严格小于 limitj 。
1.判断是否存在路径满足条件：没有给该路径施加额外的条件，比如步数什么的，所以我们可以使用并查集，将满足条件的边放入并查集中，最后判断pj和qj是否都在这个集合里，如果在，说明存在路径满足条件，返回true；反之，False。
2.对路径的唯一要求:边长度小于limitj，为了简便过程，我们可以对queries和edgeList进行升序排序，这样遍历edgeList时，当遍历到不小于limitj的边时，后面的都可以不用遍历了，后面肯定比当前的边更大或者相等，不满足条件。对queries排序，后面的limit不小于前面的，那么当前的并查集也符合后面的要求，直接在当前的基础上继续遍历edgeList即可，减少了时间复杂度。
分析代码：
先对edgeList进行按边长disi升序排序，由于一共有n个点，在进行遍历之前，每个点的父节点都是自己，所以定义一个长度为n的fa列表用来存放每个点自己的父节点（本身），定义并查集查找函数find（），实现查找目标x的根节点功能，如果目标x的父节点是自己本身，那么它就是所在集合的根节点，返回所在集合的根节点fa[x],也就是它自己；如果x的父节点不是自己，那么就查找该父节点的父节点，直到查到根节点，并把根节点赋值给x的父节点fa[x],实现路径压缩，减少查找时间。返回所在集合的根节点fa[x]。定义合并函数merge(),实现两个不相交集合合并的功能，给from_的根节点的父节点赋值为to的根节点。定义长度与queries的长度相同的值全为false的列表answer。k=0.用for循环遍历按照queries的limit升序排序的列表，i表示queries未排序时的索引，通过enumerate()函数固定为queries的key，然后对满足条件的edgeList[k][0],edgeList[k][1]进行合并集合操作，判断p,q是否在一个集合里，返回true和false给answer[i].
附:
1.sort()函数：对数组本身进行排序，还可以通过key=匿名函数指定值为关键字进行排序，本题中的e[2]就代表边长disi
2.并查集：并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。
并查集通常包含两种操作
查找(Find)：查询两个元素是否在同一个集合中
合并(Union)：把两个不相交的集合合并为一个集合
3.sorted()函数：不对数组本身进行排序，返回一个排序后的数组。

复杂度分析

时间复杂度：O ( E log E + m log m + (E + m) log n + n )，其中 E 是 edgeList 的长度，m是 queries 的长度，n 是点数。对 edgeList 和 queries 进行排序分别需要 O(ElogE) 和 O(mlogm)，并查集初始化需要 O(n)，并查集查询和合并总共需要 O((E+m)logn)。

空间复杂度：O(logE+m+n)。保存并查集需要 O(n) 的空间，保存 index 需要 O(m) 的空间，以及排序需要的栈空间。