#3244

Shortest Distance After Road Addition Queries II

international master · 2065 · lc hard +32 · 26.5% accepted · 208 likes · top 5%

⚑ DFS / BFS: Connected Components & Reachability

Description

You are given integer n and 2D integer array queries. Cities 0 to n - 1 have initial roads i -> i + 1. Each queries[i] = [ui, vi] adds road ui -> vi. No two queries have overlapping ranges.

After each query, return the shortest path from city 0 to city n - 1.

Code

1

2

3

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]: