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

标签: 并查集 图 数组 双指针 排序

难度: Hard

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

Submission

运行时间: 296 ms

内存: 56.0 MB

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rootX, rootY = self.find(x), self.find(y)
        if rootX == rootY:
            return
        
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1

def sort_edges(edge):
    return edge[2]

def sort_queries(query):
    return query[2]

class Solution:
    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:
        # Sort edges and queries by weight/limit in ascending order
        edgeList.sort(key=sort_edges)
        queries = sorted([(i, q) for i, q in enumerate(queries)], key=lambda x: x[1][2])
        
        # Initialize the union-find data structure
        uf = UnionFind(n)
        
        # Index to keep track of the current edge being processed
        edge_idx = 0
        
        # Array to store the results for each query
        results = [False] * len(queries)
        
        # Process queries in ascending order of limits
        for i, (query_idx, (p, q, limit)) in enumerate(queries):
            # Add edges with weights less than the current limit
            while edge_idx < len(edgeList) and edgeList[edge_idx][2] < limit:
                u, v, _ = edgeList[edge_idx]
                uf.union(u, v)
                edge_idx += 1
            
            # Check if p and q are connected in the union-find data structure
            if uf.find(p) == uf.find(q):
                results[query_idx] = True
        
        return results

Explain

本题解采用了排序与并查集（Union-Find）的组合策略。首先，根据边的长度和查询限制进行排序。对边按长度升序排序，对查询按限制升序排序，并在查询时附上原始索引以便最终能按顺序返回结果。使用并查集来动态维护节点间的连通性。对于每个查询，依次添加所有长度小于当前查询限制的边到并查集中，然后检查查询中的两个节点是否属于同一连通分量。如果是，则认为该查询的答案为true，否则为false。

时间复杂度: O(E log E + Q log Q)

空间复杂度: O(N + E)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rootX, rootY = self.find(x), self.find(y)
        if rootX == rootY:
            return
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
def sort_edges(edge):
    return edge[2]
def sort_queries(query):
    return query[2]
class Solution:
    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:
        edgeList.sort(key=sort_edges)  # 根据边的长度排序
        queries = sorted([(i, q) for i, q in enumerate(queries)], key=lambda x: x[1][2])  # 根据查询的限制排序并保持原索引
        uf = UnionFind(n)  # 初始化并查集
        edge_idx = 0  # 当前处理的边的索引
        results = [False] * len(queries)  # 结果数组
        for i, (query_idx, (p, q, limit)) in enumerate(queries):
            while edge_idx < len(edgeList) and edgeList[edge_idx][2] < limit:
                u, v, _ = edgeList[edge_idx]
                uf.union(u, v)
                edge_idx += 1
            if uf.find(p) == uf.find(q):
                results[query_idx] = True
        return results

Explore

在并查集中，路径压缩和秩合并是两种优化技术，主要用来提高查找和合并操作的效率。路径压缩通过在执行查找操作时减少树的高度，使后续的查找操作更快。具体来说，它使得每个节点在查找过程中直接指向其根节点。秩合并则是在执行合并操作时，总是将较低秩的树根指向较高秩的树根，如果秩相同，则选择其中一个树根作为代表，秩增加1。这样可以避免形成高度很大的树，从而保持树的平衡，减少查找路径的长度。在处理大量节点和边的场景下，这两种技术极大地提高了并查集的性能，使得几乎所有操作都能在几乎常数的时间内完成，从而有效处理大规模数据。

边按长度进行升序排序是为了便于按照查询的限制逐步添加边到并查集中。通过排序，可以确保在处理每个查询时，只考虑长度小于当前查询限制的边。这样做不仅可以按需构建并查集，还可以避免重复检查不符合条件的边，提高算法的效率。此外，这种排序还使得并查集在每次查询时都是最小的必要连通状态，避免了不必要的合并操作，从而优化了性能。

在本题解中，如果两个节点之间存在多条边，这并不会影响并查集的效率或结果的正确性。在实现中，我们只关注是否能够在给定的限制下连接两个节点，而并查集的合并操作是幂等的，即重复合并两个已经在同一连通分量中的节点不会改变并查集的状态。此外，由于边已经按长度排序，只有最短的边会被首先考虑，满足效率的需求。因此，即使存在多条边连接同一对节点，也只有最短的那些在限制内的边会被处理，不会导致重复工作或错误结果。

查询限制升序排序的目的是确保在处理每个查询时，可以逐步增加考虑的边的范围。当处理某个查询时，由于该查询的限制是当前已考虑的所有查询中最大的，因此之前处理的所有边的长度都小于或等于当前查询的限制。这意味着在处理当前查询时，不需要重新评估之前已经添加到并查集中的边，可以保证算法的正确性和效率。这种方法避免了对每个查询重复检查所有边，而是使得边的添加过程与查询的处理同步进行，提高了整体的效率。