#3243

Shortest Distance After Road Addition Queries I

specialist · 685 · lc medium +30 · 61.9% accepted · 634 likes · top 62%

⚑ DFS / BFS: Connected Components & Reachability

Description

You are given integer n and 2D integer array queries. There are n cities (0 to n - 1) with initial roads i -> i + 1. Each queries[i] = [ui, vi] adds road ui -> vi. After each query, return the shortest path length 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]: