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

Problem Explanation

The problem is a classical Graph Theory problem where we need to reorient some directed edges such that every node is visitable from node 0. We can visualize the network of cities as a directed tree where roots are formed by a one way road/connection from one city to another. The input for the problem is number of cities n and a list of connections.

We reconstruct the tree using adjacency list (represented by a 2D Array in the solution). Apart from that, we store information about edge direction. Negative index in adjacency list represents a directed edge towards node 0.

Such construction of adjacency list helps us in DFS. If we encounter a positive node during DFS, it's an edge pointing away from node 0, we increment our counter and recursively call DFS for absolute index.

Example Walk through

Consider a simple example:

n = 3, connections = [[1,0],[2,0]]

Here, we construct our adjacency list as follow:

1graph[0] = [-1, -2]  //node 1,2 are pointing towards node 0
2graph[1] = [0]        //points away from node 1
3graph[2] = [0]        //points away from node 2

When traversing the graph with DFS, we go through each nodes only once and flip the direction of the edges which points away from node 0.

In our example, all edges already point towards node 0 hence 0 edges have to be re-oriented.

Implementation

Python

1
2python
3class Solution:
4    def minReorder(self, n: int, edges: List[List[int]]) -> int:
5        adj = collections.defaultdict(list)
6        for u, v in edges:
7            adj[u].append(v)
8            adj[v].append(-u)
9        return self.dfs(0, set(), adj)
10        
11    def dfs(self, node, visited, adj):
12        visited.add(node)
13        res = 0
14        for neighbour in adj[node]:
15            if abs(neighbour) not in visited:
16                if neighbour > 0: res += 1
17                res += self.dfs(abs(neighbour), visited, adj)
18        return res

Java

1
2java
3class Solution {
4    public int minReorder(int n, int[][] connections) {
5        List<Integer>[] graph = new ArrayList[n];
6        for(int i=0;i<n;++i)
7            graph[i] = new ArrayList();
8        
9        for(int[] conn : connections){
10            graph[conn[0]].add(conn[1]);
11            graph[conn[1]].add(-conn[0]);           
12        }
13
14        return dfs(graph, 0, -1);
15    }
16    
17    private int dfs(List<Integer>[] graph, int u, int parent){
18        int change = 0;
19        for(int v: graph[u]){
20            if(Math.abs(v) == parent)    continue;
21            if(v > 0)    change++;
22            change += dfs(graph, Math.abs(v), u);
23        }
24        return change;
25    }
26}

JavaScript

1
2javascript
3class Solution {
4    constructor(n, connections) {
5        this.graph = new Array(n).fill(0).map(_ => []);
6
7        for (let [u, v] of connections) {
8            this.graph[u].push(v);
9            this.graph[v].push(-u);
10        }
11    }
12
13    minReorder() {
14        return this.dfs(0, -1);
15    }
16
17    dfs(u, parent) {
18        let change = 0;
19
20        for (let v of this.graph[u]) {
21            if(Math.abs(v) == parent) continue;
22            if (v > 0) ++change;
23            change += this.dfs(Math.abs(v), u);
24        }
25
26        return change;
27    }
28}

C++

1
2cpp
3class Solution {
4public:
5    int minReorder(int n, vector<vector<int>>& connections) {
6        vector<vector<int>> graph(n);
7
8        for (const vector<int>& conn : connections) {
9            graph[conn[0]].push_back(conn[1]);
10            graph[conn[1]].push_back(-conn[0]);  
11        }
12
13        return dfs(graph, 0, -1);
14    }
15
16private:
17    int dfs(const vector<vector<int>>& graph, int u, int parent) {
18        int change = 0;
19
20        for (const int v : graph[u]) {
21            if (abs(v) == parent)
22                continue;
23            if (v > 0)
24                ++change;
25            change += dfs(graph, abs(v), u);
26        }
27
28        return change;
29    }
30};

C#

1
2csharp
3public class Solution {
4    public int MinReorder(int n, int[][] connections) {
5        List<int>[] graph = new List<int>[n];
6        for (int i = 0; i < n; ++i)
7            graph[i] = new List<int>();
8
9        foreach (var conn in connections){
10            graph[conn[0]].Add(conn[1]);
11            graph[conn[1]].Add(-conn[0]);
12        }
13        return DFS(graph, 0, -1);
14    }
15
16    private int DFS(List<int>[] graph, int u, int parent) {
17        int change = 0;
18        foreach (var v in graph[u]){
19            if (Math.Abs(v) == parent) continue;
20            if (v > 0) change++;
21            change += DFS(graph, Math.Abs(v), u);
22        }
23
24        return change;
25    }
26}

Rust

1
2rust
3use std::collections::HashSet;
4
5impl Solution {
6    fn dfs(node: i32, mut visited: &mut HashSet<i32>, adj: &Vec<Vec<i32>>) -> usize {
7        visited.insert(node);
8        let mut res = 0;
9        for i in 0..adj[node as usize].len() {
10            let neighbour = adj[node as usize][i];
11            if !visited.contains(&neighbour.abs()) {
12                if neighbour > 0 {
13                    res += 1;
14                }
15                res += Solution::dfs(neighbour.abs(), &mut visited, &adj);
16            }
17        }
18        return res;
19    }
20
21    pub fn min_reorder(n: i32, connections: Vec<Vec<i32>>) -> i32 {
22        let mut adj = vec![vec![]; n as usize];
23        for connection in connections.iter() {
24            let u = connection[0];
25            let v = connection[1];
26            adj[u as usize].push(v);
27            adj[v as usize].push(-u);
28        }
29        let visited = &mut HashSet::new();
30        return Solution::dfs(0, visited, &adj) as i32;
31    }
32}

In this Rust solution, we create an adjacency list just like in the other solutions and then use depth first search to count the edges that need to be reversed to ensure that every node is visitable from node 0

Go

1
2go
3func dfs(node int, visited *map[int]bool, adj *[][]int) int {
4	(*visited)[node] = true
5	res := 0
6	for _, neighbour := range (*adj)[node] {
7		isVisited := (*visited)[abs(neighbour)]
8		if !isVisited {
9			if neighbour > 0 {
10				res += 1
11			}
12			res += dfs(abs(neighbour), visited, adj)
13		}
14	}
15	return res
16}
17
18func minReorder(n int, connections [][]int) int {
19	adj := make([][]int, n)
20	for _, connection := range connections {
21		u := connection[0]
22		v := connection[1]
23		adj[u] = append(adj[u], v)
24		adj[v] = append(adj[v], -u)
25	}
26	visited := make(map[int]bool)
27	return dfs(0, &visited, &adj)
28}
29
30func abs(x int) int {
31	if x < 0 {
32		return -x
33	}
34	return x
35}

In the Go solution, we use a map to keep track of the visited nodes and modify the dfs function to use the pointer of the visited map and adjacency list. This is done to avoid copying the map and the list, which would increase memory usage.

In all solutions, the time complexity is O(n) because each node and edge is visited exactly once, and the space complexity is also O(n) for storing the graph and the set of visited nodes.