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.
1import java.util.*;
2
3
We use a combination of adjacency list and iteration technique to explore each connection. Using queue mechanics, we ensure all cities are traversed, counting misaligned roads during traversal. Each road’s actual direction is evaluated for correct orientation.