Reorder Routes City Zero LeetCode 1466

LeetCode 1466 — Reorder Routes to Make All Paths Lead to the City Zero — gives you n cities numbered 0 to n-1 connected by n-1 directed roads that form a tree. The goal is to find the minimum number of roads you must reverse so that every city can reach city 0.

Because the underlying undirected structure is a tree (n nodes, n-1 edges, fully connected, no cycles), there is exactly one path between any two cities. The challenge is purely about direction — how many of those roads currently point the wrong way?

The key constraint is that you cannot add or remove roads; you can only flip their direction. Since the tree has a unique path from every node to city 0, each road either already points toward city 0 (good) or points away from it (needs reversing). Your answer is the count of roads in the wrong direction.

The core insight is to treat city 0 as the root and think of all edges as needing to point toward the root. If you root the tree at city 0, then every edge in a correctly oriented network should point from child to parent — i.e., toward city 0.

To check every edge efficiently, build an undirected adjacency list from the directed input. For each original edge (a → b), store it with a marker indicating it is an "original" direction edge. Going from a to b costs 1 reversal; going back from b to a costs 0 reversals (it already points toward a, which may be closer to root).

Now run DFS or BFS from city 0. As you traverse outward from the root, any edge you traverse in its original direction (away from city 0) means the road needs to be reversed. Sum up those costs and you have your answer.

For each directed edge (a → b) in the input, add two entries to the adjacency list: add (b, 1) to adj[a] — meaning you can go from a to b but it costs 1 reversal because this is the original direction — and add (a, 0) to adj[b] — meaning you can go from b to a for free because that direction is against the original edge, hence already correct.

The cost of 1 for the original direction and 0 for the reverse direction is the elegant trick. When DFS traverses an edge with cost 1, that edge was pointing away from root and must be counted. When it traverses an edge with cost 0, that edge already pointed toward root — no reversal needed.

The result is an undirected adjacency list where every original edge appears twice: once with cost 1 (in original direction) and once with cost 0 (in reverse direction). This lets DFS explore the full tree while automatically counting the edges that need flipping.

Starting from city 0, perform DFS. For each unvisited neighbor reachable via an edge with cost c, add c to the running total and recurse into that neighbor. Mark each node visited before recursing to prevent backtracking in the undirected representation.

The visited set is essential because the undirected adjacency list creates apparent cycles — every edge appears in both directions. Without visited tracking, DFS would oscillate between adjacent nodes forever. With it, each node is processed exactly once, giving O(n) time.

At the end of DFS, the running total is the answer: the exact number of original edges that were traversed in the away-from-root direction during the DFS — which precisely equals the number of roads that need to be reversed.

Consider n=6 with edges: 0→1, 1→3, 2→3, 4→0, 4→5. The adjacency list (with costs) becomes: adj[0]: [(1,1),(4,0)], adj[1]: [(0,0),(3,1)], adj[3]: [(1,0),(2,0)], adj[2]: [(3,1)], adj[4]: [(0,1),(5,1)], adj[5]: [(4,0)].

DFS from city 0: visit 0 → neighbor 1 via cost=1 (original, count=1) → neighbor 3 via cost=1 (original, count=2) → neighbor 2 via cost=0 (reverse, count=2). Back at 0 → neighbor 4 via cost=0 (reverse, count=2) → neighbor 5 via cost=1 (original, count=3). Final answer: 3.

Verify: reverse edges 0→1, 1→3, and 4→5 to get 1→0, 3→1, 5→4. Now paths: city 1→0, city 2→3→1→0, city 3→1→0, city 4→0, city 5→4→0. Every city reaches 0. Three reversals is indeed the minimum.

In Python, use defaultdict(list) to build the adjacency list. Each entry is a tuple (neighbor, cost) where cost=1 for original direction and cost=0 for reverse. The DFS uses a stack or recursion. Sum the costs as you traverse. Total time O(n), total space O(n) for the adjacency list and visited set.

In Java, use an ArrayList array (ArrayList<int[]>[]) of size n. Each int[] is {neighbor, cost}. Use a boolean[] visited array instead of a HashSet for speed. Iterative BFS with a Deque works identically — add neighbors to the queue with their cost and accumulate the total.

Both implementations are clean 15-20 line solutions. The graph construction loop is O(n), the DFS/BFS is O(n), and space is O(n) for the adjacency list plus O(n) for the call stack (DFS) or queue (BFS). LeetCode accepts both approaches well within time limits even at n=50,000.

Reorder Routes belongs to the tree-rerooting and directed graph family. Keys and Rooms (LeetCode 841) is a close relative — use DFS/BFS from a starting node and count how many nodes you can reach; here you reframe the problem as counting unreachable-without-reversal edges. Number of Provinces (LeetCode 547) uses the same union-find or DFS pattern on undirected graphs.

Course Schedule (LeetCode 207) and its sequel are topological sort problems on directed graphs — related because direction of edges determines validity. The DFS cycle detection in Course Schedule uses the same visited-marking discipline as Reorder Routes. Max Depth of N-ary Tree uses DFS from root outward in the same recursive style.

The common thread across all these problems: build the right graph representation first, choose DFS or BFS, and track state (visited, cost, depth) during traversal. Reorder Routes is a beautiful example where the trick is encoding edge direction as traversal cost, reducing a seemingly complex reordering problem to a simple sum.