Leetcode 1466: Reorder Routes to Make All Paths Lead to the City Zero
You are given n cities and n - 1 roads, forming a tree structure. The roads have been directed, and some roads may need to be reoriented to ensure all cities can reach the capital city (city 0). Your task is to determine the minimum number of road reorientations required to make it possible for each city to reach city 0.
Problem
Approach
Steps
Complexity
Input: The input consists of two parameters: the number of cities, n, and a list of connections, where each connection represents a directed road between two cities.
Example: Input: n = 6, connections = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]]
Constraints:
• 2 <= n <= 5 * 10^4
• connections.length == n - 1
• connections[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi
Output: The output is a single integer representing the minimum number of roads that need to be reoriented to ensure all cities can reach city 0.
Example: Output: 3
Constraints:
• The minimum number of roads that need to be reoriented.
Goal: To find the minimum number of road reorientations required for all cities to reach the capital city.
Steps:
• Construct a graph representing the cities and roads.
• For each road, if it is directed away from the capital, count it as a reorientation.
• Perform a breadth-first search (BFS) starting from the capital city, visiting each city and checking if a road needs to be reoriented to allow travel to city 0.
• Return the total number of reorientations.
Goal: The problem guarantees that each city can reach city 0 after reordering the roads.
Steps:
• The number of cities is between 2 and 5 * 10^4.
• Each city is connected by exactly one road to another city, forming a tree structure.
Assumptions:
• The input guarantees that each city can eventually reach city 0 after reordering the roads.
• All roads are directed, and the tree structure is guaranteed.
• Input: Input: n = 6, connections = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]]
• Explanation: Output: 3. To ensure that every city can reach city 0, we need to reorient three roads: from city 1 to city 0, from city 3 to city 1, and from city 4 to city 0.
• Input: Input: n = 5, connections = [[1, 0], [1, 2], [3, 2], [3, 4]]
• Explanation: Output: 2. We need to reorient the road from city 1 to city 0 and from city 2 to city 3.
Approach: The problem requires determining the minimum number of road reorientations by considering the graph structure of cities and roads. This can be efficiently solved by performing a BFS while counting roads that need to be reoriented.
Observations:
• Each road has a direction, and only roads directed away from the capital need to be reoriented.
• The graph is a tree, so there is exactly one path between any two cities.
• Using BFS ensures that we visit each city once and can track the number of reorientations needed as we traverse.
Steps:
• Construct the graph using adjacency lists.
• Mark the roads that are directed away from city 0 as needing reorientation.
• Perform BFS starting from city 0, tracking which roads need to be reoriented as we visit other cities.
• Return the count of roads that needed reorientation.
Empty Inputs:
• The input guarantees that there will be at least two cities, and n - 1 roads will be provided.
Large Inputs:
• For large inputs, we need to ensure that the BFS approach works efficiently within the given constraints of up to 5 * 10^4 cities.
Special Values:
• If the roads are already directed towards city 0, the result will be 0 (no reorientation needed).
Constraints:
• The solution must handle the upper limits of the input size efficiently.
int minReorder(int n, vector<vector<int>>& conn) {
vector<vector<int>> grid(n);
map<int, map<int, bool>> mp;
for(auto it: conn) {
grid[it[0]].push_back(it[1]);
grid[it[1]].push_back(it[0]);
mp[it[0]][it[1]] = true;
}
int cnt = 0;
queue<int> q;
q.push(0);
vector<int> vis(n, 0);
vis[0] = true;
while(!q.empty()) {
int sz = q.size();
while(sz--) {
int tmp = q.front();
q.pop();
for(int it: grid[tmp]) {
if(vis[it]) continue;
vis[it] = true;
if(mp.count(tmp) && mp[tmp].count(it)) cnt++;
q.push(it);
}
}
}
return cnt;
}
1 : Function Definition
int minReorder(int n, vector<vector<int>>& conn) {
Defines the function `minReorder` that calculates the minimum reordering needed to make all roads lead to city 0 in a directed graph.
2 : Variable Initialization
vector<vector<int>> grid(n);
Initializes a grid (adjacency list) to represent the cities and roads between them.
3 : Data Structure Initialization
map<int, map<int, bool>> mp;
Initializes a map to track the direction of roads between cities.
4 : Loop (Connections)
for(auto it: conn) {
Starts a loop to iterate through each connection in the `conn` vector.
5 : Update Grid
grid[it[0]].push_back(it[1]);
Adds a road from city `it[0]` to city `it[1]` in the grid (adjacency list).
6 : Update Grid
grid[it[1]].push_back(it[0]);
Adds a road from city `it[1]` to city `it[0]` in the grid (undirected road representation).
7 : Mark Direction
mp[it[0]][it[1]] = true;
Marks that there is a directed road from city `it[0]` to city `it[1]` in the map.
8 : Variable Initialization
int cnt = 0;
Initializes a counter `cnt` to track the number of reorders needed.
9 : Queue Initialization
queue<int> q;
Initializes a queue to perform BFS traversal starting from city 0.
10 : Enqueue Starting City
q.push(0);
Pushes city 0 onto the queue to start the BFS traversal.
11 : Visited Cities Initialization
vector<int> vis(n, 0);
Initializes a vector `vis` to keep track of visited cities.
12 : Mark Starting City as Visited
vis[0] = true;
Marks city 0 as visited.
13 : BFS Loop Start
while(!q.empty()) {
Starts a while loop that runs as long as there are cities to process in the queue.
14 : Queue Size
int sz = q.size();
Gets the size of the queue to process all cities at the current level of BFS.
15 : Inner Loop
while(sz--) {
Starts an inner loop to process each city at the current level of BFS.
16 : Dequeue City
int tmp = q.front();
Dequeues the front city from the queue for processing.
17 : Pop from Queue
q.pop();
Pops the dequeued city from the queue.
18 : Loop Through Connected Cities
for(int it: grid[tmp]) {
Loops through all cities connected to the current city `tmp`.
19 : Skip Visited Cities
if(vis[it]) continue;
If a city has already been visited, it skips processing.
20 : Mark as Visited
vis[it] = true;
Marks the current city `it` as visited.
21 : Count Road Reorders
if(mp.count(tmp) && mp[tmp].count(it)) cnt++;
Increments the counter `cnt` if the road from `tmp` to `it` is directed and needs to be reordered.
22 : Enqueue City
q.push(it);
Pushes the city `it` onto the queue for further processing.
23 : Return Statement
return cnt;
Returns the count of reorders needed to make all roads lead to city 0.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear in the number of cities because we are performing a BFS traversal over the tree, which has n - 1 edges.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the storage needed for the adjacency list and visited nodes.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus