1697.Checking Existence of Edge Length Limited Paths

tags: Hard,Array,Graph

1697. Checking Existence of Edge Length Limited Paths

題目描述

An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [

$u_i$,

$v_i$,

$di{s}_i$] denotes an edge between nodes

$u_i$ and

$v_i$ with distance

$di{s}_i$. Note that there may be multiple edges between two nodes.

Given an array queries, where queries[j] = [

$p_j$,

$q_j$,

$limi{t}_j$], your task is to determine for each queries[j] whether there is a path between

$p_j$ and

$q_j$ such that each edge on the path has a distance strictly less than

$limi{t}_j$ .

Return a boolean array answer, where answer.length == queries.length and the j^th value of answer is true if there is a path for queries[j] is true, and false otherwise.

範例

Example 1:

Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
Output: [false,true]
Explanation: The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.
For the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query.
For the second query, there is a path (0 -> 1 -> 2) of two edges with distances less than 5, thus we return true for this query.

Example 2:

Input: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
Output: [true,false]
Exaplanation: The above figure shows the given graph.

Constraints:

• 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 <=
  $di{s}_i$,
  $limi{t}_j$ <= 10⁹
• There may be multiple edges between two nodes.

解答

Python

class Solution:
    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:
        parents = list(range(n))
        ranks = [0] * n

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

        def union(x, y):
            x, y = find(x), find(y)
            if x != y:
                if ranks[x] < ranks[y]:
                    parents[x] = y
                elif ranks[x] > ranks[y]:
                    parents[y] = x
                else:
                    parents[y] = x
                    ranks[x] += 1

        ans = [False] * len(queries)
        edges = sorted(edgeList, key=lambda x: -x[2])
        queries = sorted(enumerate(queries), key=lambda x: x[1][2])
        for i, (p, q, limit) in queries:
            while len(edges) > 0 and edges[-1][2] < limit:
                u, v, _ = edges.pop()
                union(u, v)
            ans[i] = find(p) == find(q)
        return ans

Yen-Chi ChenMon, May 1, 2023

Reference

回到題目列表