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 != biProblem Overview: You are given n cities connected by n - 1 directed roads forming a tree. Some roads point away from city 0. The goal is to reverse the minimum number of roads so every city has a path leading to city 0. The core challenge is detecting which edges point in the wrong direction when traversing from the capital.
Approach 1: Depth First Search (DFS) with Edge Direction Tracking (O(n) time, O(n) space)
Convert the directed graph into an adjacency list that keeps track of edge directions. For each connection (u, v), store two entries: (u → v, needsReversal = 1) and (v → u, needsReversal = 0). This representation allows traversal in both directions while remembering whether the original edge pointed away from city 0. Start a DFS from node 0, visiting neighbors while avoiding the parent node. Each time DFS follows an edge marked with needsReversal = 1, increment the counter because that road must be reversed to allow travel toward the capital.
This works because the underlying structure is a tree, so every edge is visited exactly once. DFS naturally explores the entire graph while accumulating the number of incorrect directions. The approach relies on standard Depth-First Search traversal over a graph representation.
Approach 2: Breadth First Search (BFS) with Direction Flags (O(n) time, O(n) space)
The BFS approach uses the same adjacency representation but processes nodes level by level starting from city 0. Initialize a queue with node 0 and mark it visited. For each node dequeued, iterate through its neighbors. If the stored direction flag indicates the edge originally pointed away from the current node toward the neighbor, it must be reversed, so increment the counter.
Each neighbor is then added to the queue if it has not been visited. Because the graph is a tree with n - 1 edges, BFS visits each node once and inspects each edge once, resulting in linear time. This version is often easier to reason about when you prefer iterative traversal using a queue. It follows the classic pattern of Breadth-First Search on graphs while tracking edge orientation.
Recommended for interviews: Both DFS and BFS achieve the optimal O(n) time complexity since every node and edge is processed once. Interviewers typically expect the DFS solution because it is concise and demonstrates strong understanding of graph traversal and edge direction modeling. Showing the adjacency trick (storing both directions with a cost flag) demonstrates that you can convert a directed tree into a traversal-friendly structure. BFS is equally valid and often preferred in iterative implementations.
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.
We initialize an adjacency list to store each city's connections, differentiating directed and undirected edges. Starting from city 0, for each adjacent city, if the edge is directed away from the current city, we count it. We use a recursive DFS function to traverse the graph, keeping track of the parent to avoid cycles.
Python
JavaScript
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.
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.
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’.
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.
The route map given in the problem has n nodes and n-1 edges. If we ignore the direction of the edges, then these n nodes form a tree. The problem requires us to change the direction of some edges so that each node can reach node 0.
We might as well consider starting from node 0 and reaching all other nodes. The direction is opposite to the problem description, which means that when we build the graph, for the directed edge [a, b], we should regard it as the directed edge [b, a]. That is to say, if it is from a to b, we need to change the direction once; if it is from b to a, no direction change is needed.
Next, we only need to start from node 0, search all other nodes, and during the process, if we encounter an edge that needs to change direction, we accumulate the number of direction changes once.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the problem.
We can use the Breadth-First Search (BFS) method, starting from node 0, to search all other nodes. During the process, if we encounter an edge that requires a change of direction, we increment the count of direction changes.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the problem.
Python
| Approach | Complexity |
|---|---|
| Using Depth First Search (DFS) | 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. |
| Breadth First Search (BFS) | 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. |
| DFS | — |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Edge Direction Tracking | O(n) | O(n) | Most common interview solution. Concise recursion and natural tree traversal. |
| BFS with Direction Flags | O(n) | O(n) | Useful when preferring iterative traversal or avoiding recursion depth issues. |
Leetcode 1466 - REORDER ROUTES TO MAKE ALL PATHS LEAD TO THE CITY ZERO • NeetCode • 60,472 views views
Watch 9 more video solutions →Practice Reorder Routes to Make All Paths Lead to the City Zero with our built-in code editor and test cases.
Practice on FleetCode