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.
1def minReorder(n, connections):
2 neighbors = {i: [] for i in range(n)}
3 for u, v in connections:
4 neighbors[u].append((v, 1)) # Indicates original direction u->v
5 neighbors[v].append((u, 0)) # Virtual reverse direction
6
7 def dfs(node, parent):
8 reorder_count = 0
9 for neighbor, direction in neighbors[node]:
10 if neighbor == parent:
11 continue
12 reorder_count += direction + dfs(neighbor, node)
13 return reorder_count
14
15 return dfs(0, -1)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.
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’.