Breadth-First Visiting Order of a City Road Network
Company: Akuna Capital
Role: Quantitative Researcher
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A city network has `n` cities, numbered `0` to `n - 1`, and two-way roads between pairs of cities. Starting from a given city, return the order in which a breadth-first traversal visits the cities.
The candidate's report says only that the task outputs the traversal order of a city network and that a breadth-first search with a queue solves it; this version fixes the input format, the start city and the order in which neighbors are taken in Rules below, so that the answer is unique.
### Function Signature
```python
def bfs_visit_order(n: int, roads: list[list[int]], start: int) -> list[int]:
```
### Rules
- Each `roads[i] = [u, v]` is a two-way road between cities `u` and `v`.
- The traversal starts with only `start` in the queue, marked as visited. It repeatedly removes the city at the front of the queue and appends every neighbor of that city that has not been visited yet, in increasing order of city number, marking each one as visited as it is appended.
- The visiting order is the order in which cities enter the queue, beginning with `start`.
- Cities that cannot be reached from `start` do not appear in the output.
- Return the visiting order as a list of city numbers.
### Constraints
- `1 <= n <= 10^5`
- `0 <= len(roads) <= 2 * 10^5`
- `0 <= u, v < n` and `u != v`; no pair of cities is joined by more than one road, in either order.
- `0 <= start < n`
### Examples
**Example 1**
```text
Input: n = 6, roads = [[0, 3], [0, 1], [1, 4], [3, 4], [2, 5]], start = 0
Output: [0, 1, 3, 4]
```
From city 0, its neighbors 1 and 3 enter the queue in increasing order. City 1 then adds 4; when city 3 is processed, 0 and 4 are already visited. Cities 2 and 5 cannot be reached from 0.
**Example 2**
```text
Input: n = 5, roads = [[2, 4], [2, 0], [4, 1], [0, 3]], start = 2
Output: [2, 0, 4, 3, 1]
```
Cities 0 and 4 are one road from city 2 and enter first, 0 before 4. City 0 then adds 3, and city 4 adds 1, so 3 comes before 1 even though its number is larger.
**Example 3**
```text
Input: n = 1, roads = [], start = 0
Output: [0]
```
Overview: Return the order in which a breadth-first traversal from a start city visits a network of cities joined by two-way roads, taking neighbors in increasing order. Tests building adjacency lists, queue-based traversal, marking cities as visited at the right moment and leaving out cities that cannot be reached.
A city network has `n` cities, numbered `0` to `n - 1`, and two-way roads between pairs of cities. Each `roads[i] = [u, v]` is a two-way road between cities `u` and `v`. Starting from the city `start`, return the order in which a breadth-first traversal visits the cities.
The traversal works exactly as follows:
- The queue starts with only `start` in it, and `start` is marked as visited.
- Repeatedly remove the city at the front of the queue and append every neighbor of that city that has not been visited yet, in increasing order of city number, marking each one as visited as it is appended.
- The visiting order is the order in which cities enter the queue, beginning with `start`.
- Cities that cannot be reached from `start` do not appear in the output.
Implement `bfs_visit_order(n, roads, start)` and return the visiting order as a list of city numbers.
### Example 1
```text
Input: n = 6, roads = [[0, 3], [0, 1], [1, 4], [3, 4], [2, 5]], start = 0
Output: [0, 1, 3, 4]
```
From city 0, its neighbors 1 and 3 enter the queue in increasing order. City 1 then adds 4; when city 3 is processed, 0 and 4 are already visited. Cities 2 and 5 cannot be reached from 0.
### Example 2
```text
Input: n = 5, roads = [[2, 4], [2, 0], [4, 1], [0, 3]], start = 2
Output: [2, 0, 4, 3, 1]
```
Cities 0 and 4 are one road from city 2 and enter first, 0 before 4. City 0 then adds 3, and city 4 adds 1, so 3 comes before 1 even though its number is larger.
### Constraints
- `1 <= n <= 10^5`
- `0 <= len(roads) <= 2 * 10^5`
- `0 <= u, v < n` and `u != v`; no pair of cities is joined by more than one road, in either order.
- `0 <= start < n`
Every city number, and so every value in the output, is less than `n`, so all values fit in a 32-bit signed integer; none can exceed 2^31 - 1.
Constraints
- 1 <= n <= 10^5
- 0 <= len(roads) <= 2 * 10^5
- 0 <= u, v < n and u != v; no pair of cities is joined by more than one road, in either order.
- 0 <= start < n
Examples
Input: (6, [[0, 3], [0, 1], [1, 4], [3, 4], [2, 5]], 0)
Expected Output: [0, 1, 3, 4]
Explanation: Source Example 1: 0 adds 1 and 3 in increasing order, 1 adds 4, and 2 and 5 are in another component, so they are omitted.
Input: (5, [[2, 4], [2, 0], [4, 1], [0, 3]], 2)
Expected Output: [2, 0, 4, 3, 1]
Explanation: Source Example 2: start is 2; 3 (added by 0) comes before 1 (added by 4) although 3 > 1, so the answer is not sorted within a level.
Hints
- Every road is two-way, so a road listed as [u, v] makes each city a neighbor of the other, whichever way round it is written.
- The order in which roads are listed does not matter: when a city leaves the queue, its unvisited neighbors go in by increasing city number.
- A city counts as visited the moment it enters the queue, so a city next to several earlier cities is added only once, by the first of them to leave the queue.