Sponsored
Sponsored
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;
}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’.