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.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Graph
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 40connections.length == n - 1Ignoring direction, the roads form a tree.
Hints for Reorder Routes to Make All Paths Lead to the City Zero
Hint 1
Traverse the tree outward from city 0, walking roads in both directions.
Hint 2
Store each road twice: once as it is, once reversed, tagging which is which.
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
- Add
(b, 1)toadj[a]and(a, 0)toadj[b]for each roada → b. - 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
seencheck 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 changesJava
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)