1466. Reorder Routes to Make All Paths Lead to the City Zero

MediumDepth-First SearchBreadth-First SearchGraph

Problem Description

The problem involves a network of cities connected by roads, which can be visualized as a tree graph where each node represents a city, and each edge represents a road. The cities are numbered from 0 to n - 1, and there's a single unique path between any two cities. Initially, the roads are one-way (directed), and our goal is to ensure that every city can travel to the capital city, city 0, possibly by reorienting some roads.

Given a list connections where each connection is a pair [a_i, b_i] indicating a one-way road from city a_i to city b_i, we are tasked to determine the minimum number of roads we need to change to make the capital city reachable from all other cities. The twist here is that we treat the graph as if it's an undirected tree to traverse it, but we must keep track of the original direction of the roads because that will indicate which ones need to be reversed for the solution.

Flowchart Walkthrough

To determine the appropriate algorithm to solve LeetCode 1466. Reorder Routes to Make All Paths Lead to the City Zero, let's use the Flowchart. Here's a step-by-step analysis:

Is it a graph?

Yes: The problem involves cities and routes, which can be naturally represented as a graph where cities are nodes and routes are directed edges.

Is it a tree?

Yes: Since all paths need to lead to city zero and there are no cycles as per the problem's constraints (each city except city 0 has exactly one outgoing route), this forms a directed tree (or arborescence) rooted at city 0.

We can directly proceed to using a Depth-First Search (DFS) based on the flowchart, as the problem fittingly involves working within a tree structure to reorder or reorient the routes/edges to ensure all paths lead to a specific root node (city 0). Here, DFS is ideal for exploring each node starting from the root and making sure all paths correctly lead towards it.

The conclusion from the flowchart: DFS algorithm is suitable for traversing and reordering routes in this directed tree problem.

Intuition

The underlying concept of the solution is Depth-First Search (DFS). We employ DFS because it effectively explores all the paths from the root to the leaves in a tree, which aligns well with the nature of our problem — ensuring connectivity in a tree from every node to the root.

To solve the problem, we treat the graph as undirected to explore it freely. However, we have to remember the initial direction of the roads. Consequently, as we perform DFS starting from the capital city (node 0), we keep a set of tuples s representing the original direction of the roads.

When we traverse from one city to another, we check if we are moving in the direction originally set for the road. If we are not, this means that to achieve our goal of reorienting roads toward the capital, we will have to change the direction of this road. Thus, we increment our counter of changed roads each time we travel on a road in the direction it was not initially intended for.

The process is recursive — from each city we visit, we attempt to visit all other cities it is connected to (that we have not already visited), keeping track of the roads we need to change. The base effective case for the recursive DFS is when we have visited all cities. The sum of changed roads then gives us the minimum number of changes required to meet our goal of connectivity to the capital.

Learn more about Depth-First Search, Breadth-First Search and Graph patterns.

Solution Approach

The solution uses Depth-First Search (DFS) to walk through the cities and check if the roads need to be reoriented. The primary data structure used is a graph g, implemented as a dictionary where each key is a city and the corresponding value is a list of cities directly reachable from it. Additionally, a set s is maintained to keep track of the original directions of the roads so that while performing DFS, we can determine whether a road is traversed in the initial direction or not.

Here’s a breakdown of the key steps in the code:

Initializing the Graph:
```
g = defaultdict(list)
```
Here we initialize g as a default dictionary of lists, which will store the undirected graph.

Storing Original Direction:

s = set()
for a, b in connections:
    g[a].append(b)
    g[b].append(a)
    s.add((a, b))

For each connection in the input, we add an edge to our graph in both directions (to make it undirected), and the original direction (from a to b) is stored in set s.

Visitation Tracking:
```
vis = [False] * n
```
An array vis of boolean values is used to keep track of visited cities.

Depth-First Search (DFS):

def dfs(u):
    vis[u] = True
    ans = 0
    for v in g[u]:
        if not vis[v]:
            if (u, v) in s:
                ans += 1
            ans += dfs(v)
    return ans

The dfs function is recursively applied to traverse the graph. If we encounter a city v that has not been visited and the original direction of the road was from u to v (stored in set s), we know that we need to change this road's direction.

Returning the Result:
```
return dfs(0)
```
Finally, we start the DFS from the capital city, city 0, and the function returns the total number of road changes required to achieve the goal.

This approach ensures that we only consider each road once and return the minimum number of roads that need to be reoriented so that every city can travel to the capital.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we are given a network of 4 cities (numbered 0 to 3) with the following one-way connections:

1 -> 0
2 -> 1
3 -> 1

Here, city 0 is the capital city. According to the problem, we want every city to reach the capital city directly or indirectly, potentially by changing the direction of some roads.

Following the solution approach:

Initializing the Graph: We initialize an empty default dictionary for our graph g.

Storing Original Direction: We populate the graph to be undirected, and we store the original directions in set s:

connections = [(1, 0), (2, 1), (3, 1)]
g = defaultdict(list)
s = set()

for a, b in connections:
    g[a].append(b)
    g[b].append(a)
    s.add((a, b))

The graph g and set s now look like this:

g = {1: [0, 2, 3], 0: [1], 2: [1], 3: [1]}
s = {(1, 0), (2, 1), (3, 1)}

Visitation Tracking: We create a list vis to keep track of visited cities.

vis = [False, False, False, False]

Depth-First Search (DFS): We define the dfs function and run it from the capital city:

def dfs(u):
    vis[u] = True
    ans = 0
    for v in g[u]:
        if not vis[v]:
            if (u, v) in s:
                ans += 1
            ans += dfs(v)
    return ans

return dfs(0)

DFS begins at city 0, which visits city 1. City 1 is connected to cities 2 and 3. Since the directions (1, 2) and (1, 3) are not in set s, these roads don't have to be reversed. The road from city 1 to city 0 is in set s, and we're moving from city 1 to city 0 as intended, so we don't reverse it either.

Returning the Result: After running the DFS function starting from the capital, city 0, we can iterate through the graph and find that no road orientations need to be changed because all cities can already reach the capital directly or indirectly within the original orientation. Thus, the function would return 0, indicating no road changes are required.

Given the graph's properties as a tree and our use of DFS, each path from the leaf node to the root will be explored exactly once, ensuring the correctness and efficiency of the algorithm.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def minReorder(self, n: int, connections: List[List[int]]) -> int:
5        # Perform depth-first search to count reorders starting from node u.
6        def dfs(node):
7            visited[node] = True  # Mark the current node as visited.
8            count = 0  # Initialize the reorder count.
9
10            # Iterate over connected nodes of the current node.
11            for connected_node in adjacency_list[node]:
12                if not visited[connected_node]:
13                    # If the edge from the current node to the connected node is in
14                    # the original direction, increase the reorder count.
15                    if (node, connected_node) in directed_edges:
16                        count += 1
17                    # Add the result of recursively calling dfs on the connected node.
18                    count += dfs(connected_node)
19            return count
20
21        # Create an adjacency list and a set to store directed edges.
22        adjacency_list = defaultdict(list)
23        directed_edges = set()
24
25        # Populate the adjacency list and directed edges set.
26        for a, b in connections:
27            adjacency_list[a].append(b)
28            adjacency_list[b].append(a)
29            directed_edges.add((a, b))
30
31        # Initialize a list to keep track of visited nodes.
32        visited = [False] * n
33
34        # Start the depth-first search from node 0 and return the reorder count.
35        return dfs(0)
36

1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.HashMap;
4import java.util.List;
5import java.util.Map;
6
7class Solution {
8    // Helper class to represent a pair of values consisting of a node and a boolean indicating the edge's direction
9    public static class Edge {
10        int node;
11        boolean isDirected;
12
13        public Edge(int node, boolean isDirected) {
14            this.node = node;
15            this.isDirected = isDirected;
16        }
17    }
18
19    // Main method to find the minimum reorder.
20    // `n` represents the number of nodes, and `connections` represents the directed edges.
21    public int minReorder(int n, int[][] connections) {
22        // Create a graph represented as an adjacency list
23        Map<Integer, List<Edge>> graph = new HashMap<>();
24        for (int[] connection : connections) {
25            int from = connection[0], to = connection[1];
26            graph.computeIfAbsent(from, k -> new ArrayList<>()).add(new Edge(to, true));
27            graph.computeIfAbsent(to, k -> new ArrayList<>()).add(new Edge(from, false));
28        }
29        boolean[] visited = new boolean[n]; // Track visited nodes
30        return dfs(0, graph, visited); // Perform DFS starting from node 0
31    }
32
33    // Recursive DFS to accumulate the count of edges that need to be redirected
34    private int dfs(int currentNode, Map<Integer, List<Edge>> graph, boolean[] visited) {
35        visited[currentNode] = true; // Mark the current node as visited
36        int reorderCount = 0; // Initialize the reorder count for the current node
37        // Get the edges connected to the current node; if not present, get an empty list
38        List<Edge> edges = graph.getOrDefault(currentNode, Collections.emptyList());
39        for (Edge edge : edges) {
40            int nextNode = edge.node; // The node at the other end of the edge
41            boolean isDirected = edge.isDirected; // If the edge direction is from currentNode to nextNode
42            if (!visited[nextNode]) { // If the next node has not been visited
43                if (isDirected) {
44                    // If the current edge is directed towards the next node, it needs to be reordered.
45                    reorderCount++;
46                }
47                // Add the reorders required from deeper levels of the graph
48                reorderCount += dfs(nextNode, graph, visited);
49            }
50        }
51        return reorderCount; // Return the total count of reorderings for this branch
52    }
53}
54

1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    int minReorder(int n, vector<vector<int>>& connections) {
8        // Create a graph represented as an adjacency list where each edge also
9        // has a boolean value indicating the direction of the edge.
10        unordered_map<int, vector<pair<int, bool>>> graph;
11
12        // Populate the graph with connections, including the reverse connection
13        // but mark it as false to indicate it's not in the initial direction.
14        for (auto& edge : connections) {
15            int source = edge[0], destination = edge[1];
16            graph[source].emplace_back(destination, true); // true for original direction
17            graph[destination].emplace_back(source, false); // false for reverse
18        }
19
20        // Keep track of visited nodes to avoid revisiting them.
21        vector<bool> visited(n, false);
22
23        // Begin depth-first search from node 0. Accumulate the number of reorders along the path.
24        return dfs(0, graph, visited);
25    }
26
27private:
28    // Helper function to perform depth-first search.
29    // It returns the count of edges that need to be reversed in order
30    // to make all paths lead to city 0.
31    int dfs(int currentNode, unordered_map<int, vector<pair<int, bool>>>& graph, vector<bool>& visited) {
32        // Mark the current node as visited.
33        visited[currentNode] = true;
34      
35        // Initialize the counter for the number of reorders at the current node.
36        int reorderCount = 0;
37
38        // Explore all the neighbors of the current node.
39        for (auto& neighbor : graph[currentNode]) {
40            int nextNode = neighbor.first;  // The neighboring city
41            bool edgeDirection = neighbor.second; // True if edge is from currentNode -> nextNode
42          
43            // If the nextNode hasn't been visited, explore it.
44            if (!visited[nextNode]) {
45                // Increment reorder count if the current edge is in the wrong direction
46                if (edgeDirection) {
47                    reorderCount++;
48                }
49                // Recurse into the next node and add the reorders found there to the total count.
50                reorderCount += dfs(nextNode, graph, visited);
51            }
52        }
53
54        // Return the total reorder count for the current subtree.
55        return reorderCount;
56    }
57};
58
59// Example usage:
60// int main() {
61//     Solution solver;
62//     vector<vector<int>> connections = {{0,1}, {1,3}, {2,3}, {4,0}, {4,5}};
63//     int result = solver.minReorder(6, connections);
64//     cout << "Number of roads to be reversed: " << result << endl;
65//     return 0;
66// }
67

1import { Vector } from "prelude-ts";
2
3// A type representing the graph as an adjacency list, where each node has a list of neighbors and
4// whether the edge to that neighbor needs reordering (true) or not (false).
5type Graph = Map<number, Array<[number, boolean]>>;
6
7// The 'minReorder' function returns the minimum number of reorders required to make all roads lead to city 0.
8// Parameters:
9//     n: number - The total number of cities.
10//     connections: number[][] - The list of directed road connections between cities.
11// Returns:
12//     number - The minimum number of reordering operations.
13function minReorder(n: number, connections: number[][]): number {
14    // Initialize the graph as an empty map.
15    const graph: Graph = new Map();
16
17    // Populate the graph with connections, including the reverse connection
18    // but marked as false to indicate the reverse direction is not in the initial direction.
19    connections.forEach(connection => {
20        const [source, destination] = connection;
21      
22        if (!graph.has(source)) {
23            graph.set(source, []);
24        }
25        graph.get(source)!.push([destination, true]); // true for original direction
26      
27        if (!graph.has(destination)) {
28            graph.set(destination, []);
29        }
30        graph.get(destination)!.push([source, false]); // false for reverse
31    });
32
33    // Keep track of visited cities to avoid revisiting.
34    const visited: boolean[] = Array(n).fill(false);
35
36    // Start the depth-first search from city 0 and calculate the number of reorders.
37    return dfs(0, graph, visited);
38}
39
40// The 'dfs' function performs a depth-first search on the graph to find the reordering needed.
41// Parameters:
42//     currentNode: number - The current node in the DFS traversal.
43//     graph: Graph - The adjacency list representation of the graph, including edge directions.
44//     visited: boolean[] - An array tracking which nodes have been visited.
45// Returns:
46//     number - The count of edges that need to be reversed from the current node.
47function dfs(currentNode: number, graph: Graph, visited: boolean[]): number {
48    // Mark the current city as visited.
49    visited[currentNode] = true;
50
51    // Initialize the count for reorders from the current city.
52    let reorderCount: number = 0;
53
54    // If the graph contains the current node, explore the neighbors.
55    if (graph.has(currentNode)) {
56        // Explore all the neighboring cities of the current city.
57        graph.get(currentNode)!.forEach(neighbor => {
58            const [nextNode, edgeDirection] = neighbor;
59          
60            // Only visit unvisited neighboring cities.
61            if (!visited[nextNode]) {
62                // If the direction is wrong, we need to reorder it.
63                if (edgeDirection) {
64                    reorderCount++;
65                }
66                // Recursively call dfs for the neighboring city and add its reorders to the count.
67                reorderCount += dfs(nextNode, graph, visited);
68            }
69        });
70    }
71
72    // Return the total number of reorders from the current subtree.
73    return reorderCount;
74}
75
76/* Example usage:
77
78const connections = [[0, 1], [1, 3], [2, 3], [4, 0], [4, 5]];
79const result = minReorder(6, connections);
80console.log(`Number of roads to be reversed: ${result}`);
81
82*/
83

Time and Space Complexity

Time Complexity

The time complexity of this algorithm is O(N + E), where N is the number of nodes and E is the number of edges in the graph. The reasoning is as follows:

Building the graph (g) requires iterating over all connections once, which contributes O(E) time.
Populating the set (s) also requires a single iteration over all connections, which is again O(E).
The dfs function is called once and will visit each node exactly once. Each call to dfs involves iterating over the edges connected to the current node (u). Since each edge is considered twice in the undirected version of the graph (once for each direction), the total number of iterations for all calls to dfs is 2E, resulting in O(E) time.
The check for the existence of an edge in s is O(1) due to the nature of the set data structure.

Combining these observations, we get O(N + E) time complexity since every node and every edge is processed once in the depth-first search.

Space Complexity

The space complexity of the algorithm is O(N + E). The reasoning is as follows:

The graph g takes O(E) space since it stores an adjacency list containing all edges.
The set s will hold at most E tuples, giving O(E) space.
The visited list vis has one boolean entry per node, giving O(N) space.
The recursive stack for the depth-first search can go as deep as O(N) in the case of a path graph.

When combined, this leads to a total space complexity of O(N + E), due to the storage for the graph structure, set of directed edges, visited array, and recursion stack.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know