Problem
Given n cities numbered from0 to n - 1 and n - 1 directed roads, where connections[i] = [a, b] means there is a road from city a to city b, return the minimum number of roads that must be reordered so that every city can reach city 0.
The roads form a connected graph. Some roads may already point toward city 0, while others point away from it and need to be reversed.
Example(s)
Consider the following examples to understand the expected input and output.Example 1
Input
n = 6
connections = [[0,1], [1,3], [2,3], [4,0], [4,5]]Output
3Example 2
Input
n = 5
connections = [[1,0], [1,2], [3,2], [3,4]]Output
2Solution
This solution uses Depth-First Search (DFS) to traverse the graph starting from city 0. We store every road in both directions and use a flag to remember whether the original road points away from the current city.When the original road points from the current city to the next city, it is moving away from city 0, so it must be reversed. We count such roads while performing DFS.
class Solution {
int count = 0;
public int minReorder(int n, int[][] connections) {
List> adj = new ArrayList<>();
// Create adjacency lists
for (int i = 0; i < n; i++)
adj.add(new ArrayList<>());
for (int[] connection : connections) {
// Original direction: u -> v
adj.get(connection[0]).add(
new int[]{connection[1], 1});
// Reverse direction for traversal
adj.get(connection[1]).add(
new int[]{connection[0], 0});
}
boolean[] visited = new boolean[n];
dfs(adj, visited, 0);
return count;
}
private void dfs(List> adj,
boolean[] visited, int city) {
if (visited[city])
return;
visited[city] = true;
for (int[] connection : adj.get(city)) {
int to = connection[0];
int direction = connection[1];
if (!visited[to]) {
// Reverse road if it points away from city 0
count += direction;
dfs(adj, visited, to);
}
}
}
}
Complexity
Each city and road is visited once during DFS, so the time complexity isO(n), where n is the number of cities.
The adjacency list, visited array, and DFS recursion use
O(n) extra space.