How does two-pointer scanning help with the Checking Existence of Edge Length Limited Paths problem?

Two-pointer scanning allows us to process sorted edges and queries in tandem, efficiently answering multiple queries while avoiding redundant checks for edges already evaluated.

What is the role of union-find in this problem?

Union-find is used to track connectivity between nodes as edges are processed, ensuring we only check edges with distances that meet the query constraints.

What makes the Checking Existence of Edge Length Limited Paths problem hard?

The challenge lies in optimizing for multiple queries and efficiently managing the graph traversal without redundant computations, especially given large input sizes.

What does it mean that the problem involves 'multiple edges between nodes'?

This means that there could be more than one edge between any pair of nodes with different distances. Handling this requires careful edge selection and traversal during query processing.

How can GhostInterview help me optimize the solution for large datasets?

GhostInterview suggests techniques like sorting edges and queries and using efficient data structures such as union-find to ensure the solution remains scalable for large datasets.

#1697

Hard

auto_awesome双·指针·invariant

LeetCode 题解工作台

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

给你一个 n 个点组成的无向图边集 edgeList ，其中 edgeList[i] = [u i , v i , dis i ] 表示点 u i 和点 v i 之间有一条长度为 dis i 的边。请注意，两个点之间可能有超过一条边。给你一个查询数组 queries ，其中 queries[j…

数组双指针并查集图排序

题目描述

给你一个 n 个点组成的无向图边集 edgeList ，其中 edgeList[i] = [u_i, v_i, dis_i] 表示点 u_i 和点 v_i 之间有一条长度为 dis_i 的边。请注意，两个点之间可能有 超过一条边 。

给你一个查询数组queries ，其中 queries[j] = [p_j, q_j, limit_j] ，你的任务是对于每个查询 queries[j] ，判断是否存在从 p_j 到 q_j的路径，且这条路径上的每一条边都 严格小于 limit_j 。

请你返回一个 布尔数组 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 <= 10⁵
1 <= edgeList.length, queries.length <= 10⁵
edgeList[i].length == 3
queries[j].length == 3
0 <= u_i, v_i, p_j, q_j <= n - 1
u_i != v_i
p_j != q_j
1 <= dis_i, limit_j <= 10⁹
两个点之间可能有多条边。

lightbulb

解题思路

方法一：离线查询 + 并查集

根据题目要求，我们需要对每个查询 $queries[i]$ 进行判断，即判断当前查询的两个点 $a$ 和 $b$ 之间是否存在一条边权小于等于 $limit$ 的路径。

判断两点是否连通可以通过并查集来实现。另外，由于查询的顺序对结果没有影响，因此我们可以先将所有查询按照 $limit$ 从小到大排序，所有边也按照边权从小到大排序。

然后对于每个查询，我们从边权最小的边开始，将边权严格小于 $limit$ 的所有边加入并查集，接着利用并查集的查询操作判断两点是否连通即可。

时间复杂度 $O(m \times \log m + q \times \log q)$ ，其中 $m$ 和 $q$ 分别为边数和查询数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def distanceLimitedPathsExist(
        self, n: int, edgeList: List[List[int]], queries: List[List[int]]
    ) -> List[bool]:
        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        p = list(range(n))
        edgeList.sort(key=lambda x: x[2])
        j = 0
        ans = [False] * len(queries)
        for i, (a, b, limit) in sorted(enumerate(queries), key=lambda x: x[1][2]):
            while j < len(edgeList) and edgeList[j][2] < limit:
                u, v, _ = edgeList[j]
                p[find(u)] = find(v)
                j += 1
            ans[i] = find(a) == find(b)
        return ans

附并查集相关介绍以及常用模板：

并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的合并及查询问题。它支持两种操作：

查找（Find）：确定某个元素处于哪个子集，单次操作时间复杂度 $O(\alpha(n))$
合并（Union）：将两个子集合并成一个集合，单次操作时间复杂度 $O(\alpha(n))$

其中 $\alpha$ 为阿克曼函数的反函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。

以下是并查集的常用模板，需要熟练掌握。其中：

n 表示节点数
p 存储每个点的父节点，初始时每个点的父节点都是自己
size 只有当节点是祖宗节点时才有意义，表示祖宗节点所在集合中，点的数量
find(x) 函数用于查找 $x$ 所在集合的祖宗节点
union(a, b) 函数用于合并 $a$ 和 $b$ 所在的集合

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

p = list(range(n))
size = [1] * n

def find(x):
    if p[x] != x:
        # 路径压缩
        p[x] = find(p[x])
    return p[x]


def union(a, b):
    pa, pb = find(a), find(b)
    if pa == pb:
        return
    p[pa] = pb
    size[pb] += size[pa]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check the candidate's ability to optimize repeated computations across multiple queries.
question_mark
Look for a solid understanding of union-find and graph traversal algorithms.
question_mark
Assess how efficiently the candidate integrates sorting and two-pointer techniques into their solution.

warning

常见陷阱

外企场景

error
Failing to optimize for multiple queries by not sorting or reordering them properly.
error
Mismanaging the union-find data structure, leading to unnecessary recomputation of connected components.
error
Overcomplicating the solution by attempting brute force for each query without leveraging sorted edges.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing the solution with a depth-first search (DFS) approach instead of union-find.
arrow_right_alt
Handling cases where the edge distances are extremely large, and the graph is sparse.
arrow_right_alt
Optimizing for very large graphs with a focus on minimizing space complexity.

help

常见问题

外企场景

继续练习

#1632 矩阵转换后的排名 #1782 统计点对的数目 #2421 好路径的数目