0% completed
Problem Statement
You are given n
cities labeled from 0
to n-1
and n-1
roads, which form a tree structure. Each road is directed, meaning it has a specific direction.
These roads are represented by the array connections
, where connections[i] = [a, b]
indicates a road from city a
to city b
.
Change the direction of some roads so that every city can reach city 0
.
Return the minimum
number of edges that need to be reversed.
Examples
Example 1
- Input: n = 5, connections = [[0, 1], [1, 2], [2, 3], [4, 3]]
- Expected Output: 3
- Justification: To make all cities lead to city
0
, reverse the roads[0, 1]
,[1, 2]
and[2, 3]
. This will make the paths0 <- 1 <- 2 <- 3 <- 4
.
Example 2
- Input: n = 6, connections = [[0, 1], [2, 0], [3, 2], [4, 3], [5, 3]]
- Expected Output: 1
- Justification: To make all cities lead to city
0
, reverse the road[0, 1]
.
Example 3
- Input: n = 4, connections = [[1, 0], [2, 1], [3, 2]]
- Expected Output: 0
- Justification: All cities have path from itself to 0. So, we don't need to reverse any edge.
Constraints:
- 2 <= n <= 5 * 10<sup>4<sup>
- connections.length == n - 1
- connections[i].length == 2
- 0 <= a<sub>i</sub>, b<sub>i</sub> <= n - 1
- a<sub>i</sub> != b<sub>i</sub>
Solution
To solve this problem, we can use Depth-First Search (DFS). The key idea is to count the roads that need to be reversed to ensure all cities can reach city 0
. We will traverse the graph using DFS, starting from city 0
. During the traversal, if a road leads away from city 0
, it means we need to reverse it. We will keep a count of such roads and continue the DFS traversal to cover all cities.
This approach is effective because it leverages the properties of a tree structure (connected and acyclic) and the given constraints (every city can reach city 0
after reordering). DFS allows us to explore all possible paths efficiently, ensuring we count the minimum number of reversals needed.
Step-by-Step Algorithm
-
Create a graph representation:
- Use an adjacency list to represent the graph.
- Add both directions of each road to the adjacency list to handle undirected traversal.
- If a road is from
a
tob
, store it as(b, 1)
ina
's list and(a, 0)
inb
's list. Here,1
means the original direction needs to be reversed, and0
means no reversal is needed.
-
Initialize a set to track visited cities:
- Use a
HashSet
to keep track of visited nodes to avoid cycles.
- Use a
-
Perform DFS traversal:
- Start the DFS from city
0
. - For each neighboring city, check if it is already visited.
- If not visited, check if the road direction needs to be reversed.
- Increment the change counter if a reversal is needed.
- Recur for the neighboring cities.
- Start the DFS from city
-
Count the number of road reversals needed:
- Sum the number of reversals needed as you traverse each city.
Algorithm Walkthrough
Using the input: n = 5
, connections = [[0, 1], [1, 2], [2, 3], [4, 3]]
-
Graph Construction:
- Initialize the graph as an adjacency list.
- Add both directions for each road:
graph[0] = [(1, 1)] graph[1] = [(0, 0), (2, 1)] graph[2] = [(1, 0), (3, 1)] graph[3] = [(2, 0), (4, 0)] graph[4] = [(3, 1)]
-
Initialize visited set:
- Initialize an empty set
visited
.
- Initialize an empty set
-
DFS Traversal:
- Start DFS from node
0
.- Mark
0
as visited. - Traverse neighbors of
0
:(1, 1)
1
is not visited.- Road
(0, 1)
needs to be reversed. Increment change counter by1
. - Recur DFS from node
1
.- Mark
1
as visited. - Traverse neighbors of
1
:(0, 0)
,(2, 1)
0
is already visited.2
is not visited.- Road
(1, 2)
needs to be reversed. Increment change counter by1
. - Recur DFS from node
2
.- Mark
2
as visited. - Traverse neighbors of
2
:(1, 0)
,(3, 1)
1
is already visited.3
is not visited.- Road
(2, 3)
needs to be reversed. Increment change counter by1
. - Recur DFS from node
3
.- Mark
3
as visited. - Traverse neighbors of
3
:(2, 0)
,(4, 0)
2
is already visited.4
is not visited.- Road
(4, 3)
is in the correct direction. No change needed. - Recur DFS from node
4
.- Mark
4
as visited. - Traverse neighbors of
4
:(3, 1)
3
is already visited.
- DFS from node
4
completes. Returns 0.
- Mark
- DFS from node
3
completes. Returns 0.
- Mark
- DFS from node
2
completes. Returns 1.
- Mark
- DFS from node
1
completes. Returns 2.
- Mark
- DFS from node
0
completes. Returns 3.
- Mark
- Start DFS from node
-
Count the number of road reversals needed:
- Total number of reversals:
3
.
- Total number of reversals:
Code
Complexity Analysis
Time Complexity
The time complexity of the algorithm is O(n), where (n) is the number of cities (nodes) in the graph. This is because we are visiting each node exactly once and processing each edge (road) exactly twice (once for each direction).
Space Complexity
The space complexity of the algorithm is also O(n). This is due to the space required for:
- The adjacency list representation of the graph.
- The boolean array used to keep track of visited nodes.
- The call stack for the depth-first search (DFS) recursion, which, in the worst case, can go up to O(n) levels deep.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible