Reorder Routes to Make All Paths Lead to the City Zero

Problem

There are n cities labeled 0 to n - 1. There are n - 1 directed roads in connections, where connections[i] = [a, b] is a road from city a to city b. If you ignore the directions, the roads form a tree — every city is connected, with no cycles.

Some roads point the “wrong way.” Return the minimum number of roads whose direction must be reversed so that every city can reach city 0 by following the roads.

Examples

connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] → 3 — reverse 0→1, 1→3, 4→5 so all cities can reach 0.
connections = [[1,0],[1,2],[3,2]] → 2 — reverse 1→2 and 3→2 (equivalently the roads pointing away from 0).
connections = [[1,0],[2,0]] → 0 — both roads already point toward city 0, so nothing needs reversing.

Constraints

2 <= n <= 5 * 10^4
connections.length == n - 1; undirected, the roads form a tree.
Roads are directed; connections[i] = [a, b] means a → b.

Think about it first

Hint 1

Ignore direction and the graph is a tree rooted (conceptually) at city 0. Starting from 0 and walking outward, ask of each road: does it help you go *away* from 0 or *back toward* 0?

Hint 2

Build the graph storing, for each road, whether it's an "original" (points from parent to child, i.e. away from 0) or a "reverse" (already points toward 0). Traverse outward from 0. Every original edge you cross points the wrong way and must be reversed.

Hint 3

Use a DFS or BFS from node 0 over the undirected tree. For each neighbor you move to, if the real road goes parent→child, add 1 to the reversal count. The tree structure means you visit each city exactly once — no cycles to worry about.

TL;DR

Traverse the tree outward from city 0 (DFS or BFS); count edges that point away from 0 — those must be reversed — O(n) time, O(n) space.

Approach 1 — Traverse from 0, count outward edges (DFS)

The graph is a tree, so a single traversal from city 0 is optimal; there is no brute force worth writing. The work is in modeling direction.

Ignore direction to walk the tree, but keep each road’s true orientation. Root the tree at city 0. For every city to reach 0, every edge must point toward 0 (child→parent). As you DFS outward from 0 to a child, if the actual road runs parent→child (away from 0), it is oriented wrong and needs one reversal. Store neighbors as (neighbor, is_original), where is_original = True for the real direction a→b and False for the added reverse direction.

def minReorder(n: int, connections: list[list[int]]) -> int:
    adj = [[] for _ in range(n)]
    for a, b in connections:
        adj[a].append((b, 1))    # real road a->b : crossing a->b is "away from 0"
        adj[b].append((a, 0))    # phantom reverse b->a : free to traverse

    visited = [False] * n
    reversals = 0

    def dfs(city: int) -> None:
        nonlocal reversals
        visited[city] = True
        for nxt, is_original in adj[city]:
            if not visited[nxt]:
                reversals += is_original      # crossing an outward road costs 1
                dfs(nxt)

    dfs(0)
    return reversals

Walkthrough (connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]): DFS from 0. 0→1 uses real road 0→1 (away from 0) → +1. 1→3 uses real 1→3 → +1. 3→2 uses phantom reverse of 2→3 → +0. Back out; 0→4 uses phantom reverse of 4→0 → +0. 4→5 uses real 4→5 → +1. Total 3.

Each edge below is drawn in its real road direction. The three labeled reverse point away from 0 and must be flipped:

flowchart TD
    N0((0))
    N1((1))
    N2((2))
    N3((3))
    N4((4))
    N5((5))
    N0 -->|reverse| N1
    N1 -->|reverse| N3
    N2 --> N3
    N4 --> N0
    N4 -->|reverse| N5

Complexity: each node and each edge is visited once → O(n) time, O(n) space (adjacency list + recursion stack).

Approach 2 — BFS variant

Identical accounting, but expand from city 0 level by level with a queue. BFS is preferred here because n can be 50,000 and the tree may be a long path, so recursive DFS risks exceeding Python’s recursion limit. Use DFS when depth is safely bounded and you want shorter code.

from collections import deque

def minReorder(n: int, connections: list[list[int]]) -> int:
    adj = [[] for _ in range(n)]
    for a, b in connections:
        adj[a].append((b, 1))
        adj[b].append((a, 0))

    visited = [False] * n
    visited[0] = True
    reversals = 0
    queue = deque([0])
    while queue:
        city = queue.popleft()
        for nxt, is_original in adj[city]:
            if not visited[nxt]:
                visited[nxt] = True
                reversals += is_original
                queue.append(nxt)
    return reversals

Complexity: O(n) time, O(n) space.

Common pitfalls

Only adding the directed edge. You must store both orientations (real with a flag 1, phantom reverse with 0) so you can walk the undirected tree while still knowing each road’s true direction.
Counting inward edges. The cost is for edges pointing away from 0 (parent→child). Add is_original, not its complement.
Forgetting the visited guard. Even though it’s a tree, the phantom reverse edges make the adjacency list undirected — without visited you’d bounce back to the parent forever.
Recursion depth on a path-shaped tree. With n up to 5·10⁴, a linear chain overflows recursive DFS; use BFS or raise the recursion limit.

Pattern takeaway

For a directed tree (“all roads lead to 0”), root at the target and do one traversal, storing each edge with a direction flag so you can walk the underlying undirected tree while charging a cost for edges oriented the wrong way. The reusable trick: add both the real edge (weight/flag 1) and its reverse (flag 0) to the adjacency list, then DFS/BFS once — trees need no cycle handling beyond a visited mark.