Reorder Routes to Make All Paths Lead to the City Zero

Reorder Routes to Make All Paths Lead to the City Zero - Problem

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 forms 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 city 0. Return the minimum number of edges changed.

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

Input & Output

Example 1 — Basic Tree

$ Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]

› Output: 3

💡 Note: Start DFS from city 0. Need to reverse edges 1→3, 2→3, and 4→5 so all cities can reach city 0. Edges 0→1 and 4→0 are already pointing toward city 0.

Example 2 — Linear Chain

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

› Output: 2

💡 Note: Start from city 0. Edge 1→0 is correct (points to 0). Need to reverse 1→2 and 3→2 so cities 2 and 3 can reach city 0 through city 1.

Example 3 — Minimum Case

$ Input: n = 2, connections = [[1,0]]

› Output: 0

💡 Note: Only one edge 1→0, which already points toward city 0. No reversals needed.

Constraints

2 ≤ n ≤ 5 × 10⁴
connections.length == n - 1
connections[i].length == 2
0 ≤ a_i, b_i ≤ n - 1
a_i ≠ b_i

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Directed edges between cities, need all paths to lead to city 0

DFS Traversal

Start from city 0, track which edges point away and need reversal

Count Reversals

Total number of edges that must be reversed

Key Takeaway

🎯 Key Insight: Build undirected graph but track original directions - count edges pointing away from city 0

Asked in

a Amazon 35 M Microsoft 28 G Google 22

The key insight is to build an undirected graph but track original edge directions. Start DFS/BFS from city 0 and count edges that point away from the path to city 0 - these need reversal. Best approach is DFS traversal with direction tracking. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ BFS Traversal	O(n)	O(n)	Use BFS to traverse from city 0 and count edge reversals level by level
DFS Traversal	O(n)	O(n)	Build undirected graph and count edges that need reversal during DFS
Brute Force - Try All Combinations	O(2^n × n)	O(n)	Try all possible combinations of edge reversals

BFS Traversal — Algorithm Steps

Build undirected adjacency list with direction flags
Start BFS from city 0 using queue
For each edge traversed, count if it needs reversal
Process all levels until all cities are visited

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Queue

Start BFS from city 0, add to queue

Process Levels

Visit neighbors level by level, count wrong directions

Sum Reversals

Total count of edges needing reversal

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// Simplified C implementation
int solution(int n, int connections[][2]) {
    // This would require implementing BFS with queue in C
    return 0; // Placeholder
}

int main() {
    int n;
    scanf("%d", &n);
    
    int connections[1000][2];
    // Parsing would be needed here
    
    printf("%d\n", solution(n, connections));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

BFS visits each node and edge exactly once

✓ Linear Growth

Space Complexity

O(n)

Adjacency list, visited array, and BFS queue storage

⚡ Linearithmic Space

89.2K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler