Reorder Routes to Make All Paths Lead to the City Zero

Medium
460.

Reorder Routes to Make All Paths Lead to the City Zero

Reorder Routes to Make All Paths Lead to the City Zero is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Microsoft interviews.

There are n cities numbered 0 through n - 1 and n - 1 one-way roads; connections[i] = [a, b] is a road from a to b. Ignoring direction, the roads form a tree.

Return the minimum number of roads that must be reversed so that every city can reach city 0.

Example 1

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

Example 2

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

Example 3

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

Constraints

  • 2 <= n <= 40
  • connections.length == n - 1
  • Ignoring direction, the roads form a tree.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number}
 */
var minReorder = function(n, connections) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Reorder Routes to Make All Paths Lead to the City Zero Solution

Reorder Routes to Make All Paths Lead to the City Zero solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Reorder Routes to Make All Paths Lead to the City Zero is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Microsoft interviews.

Problem statement

There are n cities numbered 0 through n - 1 and n - 1 one-way roads; connections[i] = [a, b] is a road from a to b. Ignoring direction, the roads form a tree.

Return the minimum number of roads that must be reversed so that every city can reach city 0.

Example 1

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

Example 2

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

Example 3

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

Constraints

  • 2 <= n <= 40
  • connections.length == n - 1
  • Ignoring direction, the roads form a tree.

Hints for Reorder Routes to Make All Paths Lead to the City Zero

  1. Hint 1

    Traverse the tree outward from city 0, walking roads in both directions.

  2. Hint 2

    Store each road twice: once as it is, once reversed, tagging which is which.

  3. Hint 3

    Every road you traverse in its original direction points away from city 0 and must be flipped.

How to solve Reorder Routes to Make All Paths Lead to the City Zero

Traverse the tree from city 0 ignoring direction, storing each road both ways with a flag; every road walked in its original direction points away from 0 and must be flipped.

Approach

  1. Add (b, 1) to adj[a] and (a, 0) to adj[b] for each road a → b.
  2. DFS from 0; add the flag of every edge used to reach an unvisited node.

Why it works

In a tree there is one path from each city to 0; an edge traversed outward from 0 in its original orientation is oriented away from 0 on that path and must be reversed.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • The seen check is needed even though it is a tree, because edges are stored in both directions.

Reference solution

Python

def minReorder(n: int, connections) -> int:
    adjacency = [[] for _ in range(n)]
    for a, b in connections:
        adjacency[a].append((b, 1))
        adjacency[b].append((a, 0))
    seen = [False] * n
    seen[0] = True
    stack = [0]
    changes = 0
    while stack:
        node = stack.pop()
        for nxt, away in adjacency[node]:
            if seen[nxt]:
                continue
            seen[nxt] = True
            changes += away
            stack.append(nxt)
    return changes

Java

public static int minReorder(int n, int[][] connections) {
    List<List<int[]>> adjacency = new ArrayList<>();
    for (int i = 0; i < n; i++) adjacency.add(new ArrayList<>());
    for (int[] e : connections) {
        adjacency.get(e[0]).add(new int[]{e[1], 1});
        adjacency.get(e[1]).add(new int[]{e[0], 0});
    }
    boolean[] seen = new boolean[n];
    seen[0] = true;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);
    int changes = 0;
    while (!stack.isEmpty()) {
        int node = stack.pop();
        for (int[] entry : adjacency.get(node)) {
            if (seen[entry[0]]) continue;
            seen[entry[0]] = true;
            changes += entry[1];
            stack.push(entry[0]);
        }
    }
    return changes;
}

C++

int minReorder(int n, vector<vector<int>>& connections) {
    vector<vector<pair<int,int>>> adjacency(n);
    for (const auto& e : connections) {
        adjacency[e[0]].push_back(make_pair(e[1], 1));
        adjacency[e[1]].push_back(make_pair(e[0], 0));
    }
    vector<bool> seen(n, false);
    seen[0] = true;
    vector<int> stack;
    stack.push_back(0);
    int changes = 0;
    while (!stack.empty()) {
        int node = stack.back();
        stack.pop_back();
        for (const auto& entry : adjacency[node]) {
            if (seen[entry.first]) continue;
            seen[entry.first] = true;
            changes += entry.second;
            stack.push_back(entry.first);
        }
    }
    return changes;
}

JavaScript

var minReorder = function(n, connections) {
    const adjacency = [];
    for (let i = 0; i < n; i++) adjacency.push([]);
    for (let i = 0; i < connections.length; i++) {
        adjacency[connections[i][0]].push([connections[i][1], 1]);
        adjacency[connections[i][1]].push([connections[i][0], 0]);
    }
    const seen = [];
    for (let i = 0; i < n; i++) seen.push(false);
    seen[0] = true;
    const stack = [0];
    let changes = 0;
    while (stack.length > 0) {
        const node = stack.pop();
        for (let i = 0; i < adjacency[node].length; i++) {
            const next = adjacency[node][i][0];
            const away = adjacency[node][i][1];
            if (seen[next]) continue;
            seen[next] = true;
            changes += away;
            stack.push(next);
        }
    }
    return changes;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)