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

MediumDepth-First SearchBreadth-First SearchGraph
Leetcode Link

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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

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:

  1. Initializing the Graph:

    1g = defaultdict(list)

    Here we initialize g as a default dictionary of lists, which will store the undirected graph.

  2. Storing Original Direction:

    1s = set()
2for a, b in connections:
3    g[a].append(b)
4    g[b].append(a)
5    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.

  3. Visitation Tracking:

    1vis = [False] * n

    An array vis of boolean values is used to keep track of visited cities.

  4. Depth-First Search (DFS):

    1def dfs(u):
2    vis[u] = True
3    ans = 0
4    for v in g[u]:
5        if not vis[v]:
6            if (u, v) in s:
7                ans += 1
8            ans += dfs(v)
9    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.

  5. Returning the Result:

    1return 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.

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

Which data structure is used in a depth first search?

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:

11 -> 0
22 -> 1
33 -> 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:

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

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

    1connections = [(1, 0), (2, 1), (3, 1)]
2g = defaultdict(list)
3s = set()
4
5for a, b in connections:
6    g[a].append(b)
7    g[b].append(a)
8    s.add((a, b))

    The graph g and set s now look like this:

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

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

    1vis = [False, False, False, False]

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

    1def dfs(u):
2    vis[u] = True
3    ans = 0
4    for v in g[u]:
5        if not vis[v]:
6            if (u, v) in s:
7                ans += 1
8            ans += dfs(v)
9    return ans
10
11return 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.

  5. 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ