There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.
Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.
This year, there will be a big event in the capital (city 0), and many people want to travel to this city.
Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.
It's guaranteed that each city can reach city 0 after reorder.
Example 1:
Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]] Output: 3 Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
Example 2:
Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]] Output: 2 Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).
Example 3:
Input: n = 3, connections = [[1,0],[2,0]] Output: 0
Constraints:
2 <= n <= 5 * 104connections.length == n - 1connections[i].length == 20 <= ai, bi <= n - 1ai != biIn #1466 Reorder Routes to Make All Paths Lead to the City Zero, the goal is to determine the minimum number of directed roads that must be reversed so every city can reach city 0. The key observation is that while the roads are directed, the cities themselves form a connected graph.
A common strategy is to convert the graph into an augmented adjacency list. For every road a → b, store two entries: one indicating the original direction and another representing the reverse connection. Then perform a DFS or BFS traversal starting from city 0. During traversal, if you move along an edge that originally points away from city 0, it must be reversed, so you increment the counter.
This traversal ensures every node is visited once while tracking edges that require reordering. Because the graph is processed linearly, the algorithm runs efficiently with O(n) time complexity and uses O(n) space for the adjacency structure and visited tracking.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS traversal with directed edge tracking | O(n) | O(n) |
| BFS traversal with adjacency list | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Treat the graph as undirected. Start a dfs from the root, if you come across an edge in the forward direction, you need to reverse the edge.
To solve this problem, we can use a Depth First Search (DFS) starting from the capital city (city 0). During this traversal, we'll count the roads that need to be reordered.
We perform a DFS from city 0. For every road from a city a to b, we check if it's currently directed from 0 to n-1. If so, we need to count it as a reordering. Otherwise, we just traverse further.
Time Complexity: O(n), where n is the number of cities, as each node is visited exactly once.
Space Complexity: O(n), the space used for the recursion stack and storing the graph structure.
1function minReorder(n, connections) {
2 const graph = Array.from({length: n}, () => []);
3 for (const [u, v] of connections) {
4 graph[u].push([v, 1]); // original direction
5 graph[v].push([u, 0]); // virtual reverse
6 }
7
8 function dfs(city, parent) {
9 let changes = 0;
10 for (const [next, direction] of graph[city]) {
11 if (next !== parent) {
12 changes += direction + dfs(next, city);
13 }
14 }
15 return changes;
16 }
17
18 return dfs(0, -1);
19}We build graph using adjacency list capturing not only the connections but also their original direction. By invoking DFS from node 0, any time we traverse a connection that's originally directed away from node 0, it's counted as needing reordering. The recursion ensures all nodes are visited without cycles forming.
An alternate approach using BFS begins at the capital city 0. We iterate over the child nodes, making direction checks immediately. This iterative form may help memory constraints on deep trees. We change direction whenever a node is reached by an edge that has to be flipped to reach city 0.
Time Complexity: O(n) - due to a systematic BFS on each city.
Space Complexity: O(n) due to additional space for visited nodes and queued elements.
1#include <vector>
2#include <queue>
3
4using namespace std;
5
int minReorder(int n, vector<vector<int>>& connections) {
vector<vector<pair<int, int>>> graph(n);
for (const auto& con : connections) {
graph[con[0]].emplace_back(con[1], 1);
graph[con[1]].emplace_back(con[0], 0);
}
queue<int> q;
vector<bool> visited(n, false);
visited[0] = true;
q.push(0);
int reorders = 0;
while (!q.empty()) {
int node = q.front(); q.pop();
for (const auto& [next, direction] : graph[node]) {
if (!visited[next]) {
visited[next] = true;
reorders += direction;
q.push(next);
}
}
}
return reorders;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
City 0 is the destination that every other city must reach. Starting the traversal from city 0 ensures we examine how each road connects relative to this root and identify which edges must be reversed.
Yes, this problem reflects common graph traversal patterns used in technical interviews. Variants involving edge directions, DFS/BFS, and graph restructuring frequently appear in FAANG-style coding interviews.
An adjacency list is the most efficient data structure for representing the graph. It allows quick traversal of neighbors while also storing whether an edge follows the original direction or represents a reverse connection.
The optimal approach is to treat the problem as a graph traversal using DFS or BFS starting from city 0. By storing edge directions in the adjacency list, you can detect when a road points away from city 0 and count it as a required reversal.
We use a queue to facilitate BFS traversal starting from city 0. While traversing, any edge that is oriented in the non-desired direction is counted. Each node is visited only once, avoiding cycles and performing necessary reorientation counting ‘on the fly’.