Reorder Routes to Make All Paths Lead to the City Zero

Problem in plain words

There are n cities and exactly n - 1 one-way roads, and if you ignore directions the roads form a tree (every city is connected, no cycles). Each road [a, b] lets you drive from a to b only. Find the smallest number of roads whose direction you must flip so that every city can drive to city 0.

Example: n = 4, roads 0 → 1, 2 → 1, 3 → 0. The road 0 → 1 points away from 0 and must be flipped. Then 2 → 1 → 0 and 3 → 0 already work, so the answer is 1.

Intuition

Because the underlying graph is a tree, there is exactly one path between city 0 and any other city. Explore outward from city 0. Every time you cross a road in its original direction you are moving away from 0, which means cars on that road would drive away from the capital — it must be flipped. Crossing a road against its direction means it already points toward 0. So store each road twice: the original direction with cost 1 and the reverse with cost 0, then add up the costs of the edges used by a BFS from 0.

Approach

1. Build an adjacency list. For each road [a, b], add (b, 1) to a's list and (a, 0) to b's list.
2. BFS (or DFS) from city 0 with a visited array.
3. When you move from city to an unvisited neighbour through an edge with cost c, add c to the answer.
4. Return the total once all cities are visited.

Dry run

Roads 0 → 1, 2 → 1, 3 → 0.

Java solution

class Solution {
    public int minReorder(int n, int[][] connections) {
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] road : connections) {
            graph.get(road[0]).add(new int[] {road[1], 1}); // original direction
            graph.get(road[1]).add(new int[] {road[0], 0}); // reverse, already fine
        }
        boolean[] visited = new boolean[n];
        Deque<Integer> queue = new ArrayDeque<>();
        visited[0] = true;
        queue.offer(0);
        int flips = 0;
        while (!queue.isEmpty()) {
            int city = queue.poll();
            for (int[] edge : graph.get(city)) {
                int next = edge[0];
                if (!visited[next]) {
                    visited[next] = true;
                    flips += edge[1];
                    queue.offer(next);
                }
            }
        }
        return flips;
    }
}

Python solution

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
        for a, b in connections:
            graph[a].append((b, 1))  # original direction: needs a flip
            graph[b].append((a, 0))  # reverse direction: already points to 0
        visited = [False] * n
        visited[0] = True
        queue = deque([0])
        flips = 0
        while queue:
            city = queue.popleft()
            for nxt, cost in graph[city]:
                if not visited[nxt]:
                    visited[nxt] = True
                    flips += cost
                    queue.append(nxt)
        return flips

Complexity

Edge cases and common mistakes

• Only storing original directions — then you cannot reach cities whose roads point toward 0. Store both directions with different costs.
• Swapping the costs — moving outward along an original edge is what needs flipping, so the original direction carries cost 1.
• Recursion depth — with up to 5·10^4 cities in a line, recursive DFS can overflow; BFS or an explicit stack is safer.