> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Reorder Routes to Make All Paths Lead to the

> Tested Python solution for LeetCode 1466 with 29 pytest cases. Generate a practice environment with lcpy.

LeetCode 1466, [Medium](/catalog/medium). Topics: [Depth-First Search](/catalog/topics/depth-first-search), [Breadth-First Search](/catalog/topics/breadth-first-search), [Graph Theory](/catalog/topics/graph-theory). [View on LeetCode](https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/description/).

Generate this problem as a practice environment: tested reference solution, 29 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1466   # by problem number
lcpy gen -s reorder_routes_to_make_all_paths_lead_to_the_city_zero   # by problem name
```

## Problem

There are `n` cities numbered from `0` to `n - 1` and `n - 1` roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by `connections` where `connections[i] = [ai, bi]` represents a road from city `ai` to city `bi`.

This year, there will be a big event in the capital (city `0`), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city `0`. Return the **minimum** number of edges changed.

It's **guaranteed** that each city can reach city `0` after reorder.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2020/05/13/sample_1_1819.png)

```
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
```

**Explanation:** Change the direction of edges show in red such that each node can reach the node 0 (capital).

![Example 2](https://assets.leetcode.com/uploads/2020/05/13/sample_2_1819.png)

```
Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
```

**Explanation:** Change the direction of edges show in red such that each node can reach the node 0 (capital).

```
Input: n = 3, connections = [[1,0],[2,0]]
Output: 0
```

### Constraints

* `2 <= n <= 5 * 10^4`
* `connections.length == n - 1`
* `connections[i].length == 2`
* `0 <= ai, bi <= n - 1`
* `ai != bi`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/reorder_routes_to_make_all_paths_lead_to_the_city_zero/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/reorder_routes_to_make_all_paths_lead_to_the_city_zero/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import defaultdict, deque


class Solution:
    # Time: O(n)
    # Space: O(n)
    def min_reorder(self, n: int, connections: list[list[int]]) -> int:
        adjacency: dict[int, list[tuple[int, int]]] = defaultdict(list)
        for src, dst in connections:
            adjacency[src].append((dst, 1))
            adjacency[dst].append((src, 0))

        flips = 0
        visited = [False] * n
        visited[0] = True
        queue: deque[int] = deque([0])
        while queue:
            city = queue.popleft()
            for neighbor, directed_out in adjacency[city]:
                if visited[neighbor]:
                    continue
                flips += directed_out
                visited[neighbor] = True
                queue.append(neighbor)
        return flips
```

## Complexity

| Time | Space |
| - | - |
| O(n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.