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

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)

There’s no wasteful brute force worth writing here: the graph is a tree, so a single traversal from city 0 is already optimal. The key is modeling direction.

The insight: ignore direction to walk the tree, but remember each road’s true orientation. Root the tree at city 0. For every city to reach 0, every edge must ultimately 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’s 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.

class Solution:
    def minReorder(self, 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.

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

Approach 2 — BFS variant

The insight: 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 — recursive DFS would risk exceeding Python’s recursion limit. DFS is preferred when depth is safely bounded and you want the shorter code.

from collections import deque

class Solution:
    def minReorder(self, 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.