Reorder Routes to Make All Paths Lead to the City Zero

Problems

There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.

Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.

This year, there will be a big event in the capital (city 0), and many people want to travel to this city.

Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.

It’s guaranteed that each city can reach city 0 after reorder.

Examples

Example 1:

graph LR
    A(0)
    B(1)
    C(2)
    D(3)
    E(4)
    F(5)

    A -->|❌| B
    B -->|❌| D
    C --> D
    A ~~~ E --> A
    E -->|❌| F
    
    %% Corrected edges (after reversal)
    B -.->|✓| A
    D -.->|✓| B
    F -.->|✓| E
    
    linkStyle 0 stroke:#ff0000,stroke-width:3px
    linkStyle 1 stroke:#ff0000,stroke-width:3px
    linkStyle 2 stroke:#00aa00,stroke-width:2px
    linkStyle 4 stroke:#00aa00,stroke-width:2px
    linkStyle 5 stroke:#ff0000,stroke-width:3px
    linkStyle 6 stroke:#00aa00,stroke-width:2px
    linkStyle 7 stroke:#00aa00,stroke-width:2px
    linkStyle 8 stroke:#00aa00,stroke-width:2px,stroke-dasharray: 5 5

1
2
3


Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: ❌ edges need reversal (red), solid green edges are correct, dashed green edges show corrected directions. Change the direction such that each node can reach the node 0 (capital).

Example 2:

graph LR
    A(0)
    B(1)
    C(2)
    D(3)
    E(4)

    A ~~~ B --> A
    B -->|❌| C
    D --> C
    D -->|❌| E
    
    %% Corrected edges (after reversal)
    C -.->|✓| B
    E -.->|✓| D
    
    linkStyle 2 stroke:#ff0000,stroke-width:3px
    linkStyle 4 stroke:#ff0000,stroke-width:3px
    linkStyle 1 stroke:#00aa00,stroke-width:2px
    linkStyle 3 stroke:#00aa00,stroke-width:2px
    linkStyle 5 stroke:#00aa00,stroke-width:2px,stroke-dasharray: 5 5
    linkStyle 6 stroke:#00aa00,stroke-width:2px,stroke-dasharray: 5 5

1
2
3


Input: n = 5, connections = [[1,0],[1,2],[3,2],[3,4]]
Output: 2
Explanation: ❌ edges need reversal (red), solid green edges are correct, dashed green edges show corrected directions.Change the direction of edges such that each node can reach the node 0 (capital).

Example 3:

1
2


Input: n = 3, connections = [[1,0],[2,0]]
Output: 0

Solution

Method 1 – BFS with Edge Direction Tracking

Intuition

First of all, the graph cannot have cycles, as guaranteed by the problem statement (the network forms a tree).

We start from node 0 and check if all its neighbors can reach 0. If not, we reorient the necessary edges.

For example, here we see that node 1 cannot reach 0, so we fix it.

graph TB
subgraph S1[" "]
    A(0)
    B(1)
    C(2)
    D(3)
    E(4)
    F(5)
    A(0)
    A --> B:::red
    A ~~~ E --> A
    B --> D
    C --> D
    E --> F
end

subgraph S2[" "]
    A2(0)
    B2(1)
    C2(2)
    D2(3)
    E2(4)
    F2(5)
    A2(0)
    A2 -->|❌| B2:::green
    A2 ~~~ E2 --> A2
    B2 --> D2
    C2 --> D2
    E2 --> F2
    
    B2 -.->|✓| A2
end
   
S1 --> S2 
classDef red fill:#FF0000,stroke:#000,stroke-width:1px,color:#fff;    
classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff;

But node 4 can already reach 0.

graph LR
    A(0)
    B(1)
    C(2)
    D(3)
    E(4):::green
    F(5)
    A(0)
    A --> B
    A ~~~ E --> A
    B --> D
    C --> D
    E --> F

classDef red fill:#FF0000,stroke:#000,stroke-width:1px,color:#fff;    
classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff;

Now we check if 4’s neighbor can reach it. If not, we fix it.

graph TB
subgraph S1[" "]
    A(0)
    B(1)
    C(2)
    D(3)
    E(4)
    F(5):::red
    A(0)
    A -->|❌| B
    A ~~~ E --> A
    B --> D
    C --> D
    E --> F
    
    B -.->|✓| A
end

subgraph S2[" "]
    A2(0)
    B2(1)
    C2(2)
    D2(3)
    E2(4)
    F2(5):::green
    A2(0)
    A2 -->|❌| B2
    A2 ~~~ E2 --> A2
    B2 --> D2
    C2 --> D2
    
    E2 -->|❌| F2
    B2 -.->|✓| A2
    F2 -.->|✓| E2
end
   
S1 --> S2 
classDef red fill:#FF0000,stroke:#000,stroke-width:1px,color:#fff;    
classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff;

Now, check if 1’s neighbor can reach it. If not, we fix it.

graph TB
subgraph S1[" "]
    A(0)
    B(1)
    C(2)
    D(3):::red
    E(4)
    F(5)
    A(0)
    A -->|❌| B
    A ~~~ E --> A
    B --> D
    C --> D
    E --> F
    
    B -.->|✓| A
end

subgraph S2[" "]
    A2(0)
    B2(1)
    C2(2)
    D2(3):::green
    E2(4)
    F2(5)
    A2(0)
    A2 -->|❌| B2
    A2 ~~~ E2 --> A2
    B2 -->|❌| D2
    C2 --> D2
    
    E2 -->|❌| F2
    B2 -.->|✓| A2
    F2 -.->|✓| E2
    D2 -.->|✓| B2
end
   
S1 --> S2 
classDef red fill:#FF0000,stroke:#000,stroke-width:1px,color:#fff;    
classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff;

Can 3’s neighbor reach it? Yes. Can 2’s neighbor reach it? No neighbors remaining.

Now, the graph is directed, but we use one trick: we mark the graph as undirected for traversal, but remember the original direction of each edge. This allows us to count how many edges need to be reversed as we perform a BFS from city 0.

To ensure all cities can reach city 0, we need to reorient the minimum number of roads. By treating the graph as undirected for traversal but remembering the original direction of each edge, we can count how many edges need to be reversed as we perform a BFS from city 0.

Approach

Build an undirected graph, but for each edge, record whether it was originally directed away from the current node.
Start BFS from city 0, marking nodes as visited.
For each neighbor, if the edge is directed away from the current node (i.e., needs to be reversed), increment the answer.
Continue until all nodes are visited.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
class Solution {
public:
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<vector<pair<int,bool>>> g(n);
        for (auto& e : connections) {
            g[e[0]].emplace_back(e[1], true);  // original direction
            g[e[1]].emplace_back(e[0], false); // artificial reverse
        }
        vector<bool> vis(n);
        queue<int> q; q.push(0); vis[0] = true;
        int ans = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& [v, rev] : g[u]) {
                if (vis[v]) continue;
                if (rev) ans++;
                vis[v] = true;
                q.push(v);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


func minReorder(n int, connections [][]int) int {
    g := make([][][2]int, n)
    for _, e := range connections {
        g[e[0]] = append(g[e[0]], [2]int{e[1], 1})
        g[e[1]] = append(g[e[1]], [2]int{e[0], 0})
    }
    vis := make([]bool, n)
    q := []int{0}
    vis[0] = true
    ans := 0
    for len(q) > 0 {
        u := q[0]; q = q[1:]
        for _, e := range g[u] {
            v, rev := e[0], e[1]
            if vis[v] { continue }
            if rev == 1 { ans++ }
            vis[v] = true
            q = append(q, v)
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


import java.util.*;
class Solution {
    static class Dest {
        int v; boolean isArtificial;
        Dest(int v, boolean artificial) { this.v = v; this.isArtificial = artificial; }
    }
    public int minReorder(int n, int[][] connections) {
        Map<Integer, Set<Dest>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) graph.put(i, new HashSet<>());
        for (int[] e : connections) {
            int u = e[0], v = e[1];
            graph.get(v).add(new Dest(u, false));
            graph.get(u).add(new Dest(v, true));
        }
        boolean[] vis = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.add(0); vis[0] = true;
        int ans = 0;
        while (!q.isEmpty()) {
            int curr = q.poll();
            for (Dest nei : graph.get(curr)) {
                if (vis[nei.v]) continue;
                if (nei.isArtificial) ans++;
                vis[nei.v] = true;
                q.offer(nei.v);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


import java.util.*
class Solution {
    data class Dest(val v: Int, val isArtificial: Boolean)
    fun minReorder(n: Int, connections: Array<IntArray>): Int {
        val graph = Array(n) { mutableSetOf<Dest>() }
        for (e in connections) {
            graph[e[0]].add(Dest(e[1], true))
            graph[e[1]].add(Dest(e[0], false))
        }
        val vis = BooleanArray(n)
        val q: Queue<Int> = LinkedList()
        q.add(0); vis[0] = true
        var ans = 0
        while (q.isNotEmpty()) {
            val curr = q.poll()
            for (nei in graph[curr]) {
                if (vis[nei.v]) continue
                if (nei.isArtificial) ans++
                vis[nei.v] = true
                q.add(nei.v)
            }
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


from collections import deque, defaultdict
class Solution:
    def minReorder(self, n: int, connections: list[list[int]]) -> int:
        g = defaultdict(list)
        for u, v in connections:
            g[u].append((v, 1))
            g[v].append((u, 0))
        vis = [False] * n
        q = deque([0])
        vis[0] = True
        ans = 0
        while q:
            u = q.popleft()
            for v, rev in g[u]:
                if vis[v]: continue
                if rev: ans += 1
                vis[v] = True
                q.append(v)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


use std::collections::{VecDeque, HashMap};
impl Solution {
    pub fn min_reorder(n: i32, connections: Vec<Vec<i32>>) -> i32 {
        let mut g: HashMap<i32, Vec<(i32, i32)>> = HashMap::new();
        for e in &connections {
            g.entry(e[0]).or_default().push((e[1], 1));
            g.entry(e[1]).or_default().push((e[0], 0));
        }
        let mut vis = vec![false; n as usize];
        let mut q = VecDeque::new();
        q.push_back(0); vis[0] = true;
        let mut ans = 0;
        while let Some(u) = q.pop_front() {
            for &(v, rev) in g.get(&(u as i32)).unwrap_or(&vec![]) {
                if vis[v as usize] { continue; }
                if rev == 1 { ans += 1; }
                vis[v as usize] = true;
                q.push_back(v as usize);
            }
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


function minReorder(n: number, connections: number[][]): number {
    const g: [number, number][][] = Array.from({length: n}, () => []);
    for (const [u, v] of connections) {
        g[u].push([v, 1]);
        g[v].push([u, 0]);
    }
    const vis = Array(n).fill(false);
    const q: number[] = [0];
    vis[0] = true;
    let ans = 0;
    while (q.length) {
        const u = q.shift()!;
        for (const [v, rev] of g[u]) {
            if (vis[v]) continue;
            if (rev) ans++;
            vis[v] = true;
            q.push(v);
        }
    }
    return ans;
}

Complexity

⏰ Time complexity: O(N) where N is the number of cities (since the graph is a tree with N-1 edges).
🧺 Space complexity: O(N) for the graph and visited structures.

Problems#

Examples#

Solution#

Method 1 – BFS with Edge Direction Tracking#

Intuition#

Approach#

Code#

Complexity#