Reorder Routes to Make All Paths Lead to the City Zero Visualizer & Step-by-Step Algorithm Solution

Reorient the minimum number of directed roads in an n-city tree network so that every city has a path leading to capital city 0 using DFS traversal outwards from 0.

Category: graphs | Difficulty: Medium

Tags: Graph, DFS, Tree, Directed Graph

Reorder Routes to Make All Paths Lead to the City Zero

Drag nodes to arrange
CITY NETWORK (6 CITIES) ยท CAPITAL IS CITY 0
0
CAPITAL: 0
1
2
3
4
5
100%
state
capital0
currentCity-
reorientedCount0 road(s)
visitedCities0/6
Initialization
1/23
Explanation

Initialize network with 6 cities and 5 directed roads. Capital City 0 is located at the top.

Source Code
1function minReorder(n, connections) {
2 const adjacency = Array.from({ length: n }, () => []);
3 const visited = Array(n).fill(false);
4 let required = 0;
5 for (let [from, to] of connections) {
6 adjacency[from].push([to, 1]);
7 adjacency[to].push([from, 0]);
8 }
9 function dfs(city) {
10 visited[city] = true;
11 for (let [neighbour, need] of adjacency[city]) {
12 if (!visited[neighbour]) {
13 required += need;
14 dfs(neighbour);
15 }
16 }
17 }
18 dfs(0);
19 return required;
20}