Reorder Routes to Make All Paths Lead to the City Zero
Problem link: https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/
Problem Statement
There are n cities numbered from 0 to n-1 and n-1 roads such that there is exactly one path between any two cities.
Each road is directed. You need to reorder some roads so that every city can reach city 0.
Return the minimum number of edges that need to be reversed.
Input
n = number of cities connections = list of directed edges [a, b] meaning a → b
Output
Return minimum number of edges to reverse so all nodes can reach city 0.
Example
Input: n = 6 connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation
We start DFS from node 0.
If an edge goes away from 0 (wrong direction), we need to reverse it. If it already points towards 0, no change needed.
Brute Force
Intuition
Try reversing different combinations of edges and check if all nodes can reach 0. This is inefficient due to exponential possibilities.
Approach
- Generate all combinations of edge reversals
- For each configuration:
- Check if all nodes can reach 0
- Return minimum reversals
Dry Run
Too many combinations. Not scalable.
Code (Java)
// Not practical brute force
Complexity Analysis
Each edge can be reversed or not → exponential possibilities.
Optimal Solution
Intuition
Treat graph as undirected for traversal, but track original directions.
While doing DFS from node 0:
- If edge is in forward direction (away from 0), increment count
- If edge is backward (towards 0), no action needed
Approach
- Build two adjacency lists:
- forwardEdges (original direction)
- backwardEdges (reverse direction)
- Start DFS from node 0
- For each forward edge → increment answer
- For backward edges → just traverse
- Use visited array to avoid cycles
Dry Run
Start from 0 → go to neighbors If edge direction is away → ans++ Continue DFS until all nodes visited
Code (Java)
import java.util.*;
class Solution {
int ans = 0;
private void dfs(int node, boolean[] visited, List<Integer>[] forwardEdges, List<Integer>[] backwardEdges) {
visited[node] = true;
for (int ngh : forwardEdges[node]) {
if (!visited[ngh]) {
ans++; // wrong direction
dfs(ngh, visited, forwardEdges, backwardEdges);
}
}
for (int ngh : backwardEdges[node]) {
if (!visited[ngh]) {
dfs(ngh, visited, forwardEdges, backwardEdges);
}
}
}
public int minReorder(int n, int[][] connections) {
boolean[] visited = new boolean[n];
List<Integer>[] forwardEdges = new ArrayList[n];
List<Integer>[] backwardEdges = new ArrayList[n];
for (int i = 0; i < n; i++) {
forwardEdges[i] = new ArrayList<>();
backwardEdges[i] = new ArrayList<>();
}
for (int[] edge : connections) {
int a = edge[0], b = edge[1];
forwardEdges[a].add(b);
backwardEdges[b].add(a);
}
dfs(0, visited, forwardEdges, backwardEdges);
return ans;
}
}
Complexity Analysis
Each node and edge is visited once during DFS.
Quick Revision (Brute Force)
- Try all edge reversals
- Check reachability
- Exponential time
Quick Revision (Optimal)
- DFS from node 0
- Count forward edges
- Ignore backward edges