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

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

✓ BFS Traversal

⏱️ Time: O(n) Space: O(n)

Build undirected graph with edge direction tracking. Use BFS starting from city 0 to visit all cities level by level, counting edges that need reversal.

Brute Force - Try All Combinations

⏱️ Time: O(2^n × n) Space: O(n)

Generate all possible subsets of edges to reverse and check which gives minimum reversals while ensuring all nodes can reach city 0.

DFS Traversal

⏱️ Time: O(n) Space: O(n)

Create an undirected graph but track original edge directions. Start DFS from city 0 and count how many edges point away from the path to city 0.

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>

#define MAX_N 50000

typedef struct {
    int neighbor;
    int cost;
} Edge;

int solution(int n, int connections[][2], int conn_count) {
    // Dynamically allocate arrays
    Edge **graph = malloc(n * sizeof(Edge*));
    int *graph_size = calloc(n, sizeof(int));
    bool *visited = calloc(n, sizeof(bool));
    int *queue = malloc(n * sizeof(int));
    
    for (int i = 0; i < n; i++) {
        graph[i] = malloc(n * sizeof(Edge));
    }
    
    // Build undirected graph with direction tracking
    for (int i = 0; i < conn_count; i++) {
        int a = connections[i][0];
        int b = connections[i][1];
        
        // Original direction, needs reversal
        graph[a][graph_size[a]].neighbor = b;
        graph[a][graph_size[a]].cost = 1;
        graph_size[a]++;
        
        // Reverse direction, no reversal needed
        graph[b][graph_size[b]].neighbor = a;
        graph[b][graph_size[b]].cost = 0;
        graph_size[b]++;
    }
    
    // BFS
    int front = 0, rear = 0;
    queue[rear++] = 0;
    visited[0] = true;
    int reversals = 0;
    
    while (front < rear) {
        int node = queue[front++];
        
        for (int i = 0; i < graph_size[node]; i++) {
            int neighbor = graph[node][i].neighbor;
            int needsReverse = graph[node][i].cost;
            
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                reversals += needsReverse;
                queue[rear++] = neighbor;
            }
        }
    }
    
    // Free memory
    for (int i = 0; i < n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graph_size);
    free(visited);
    free(queue);
    
    return reversals;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[100000];
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    
    int connections[MAX_N][2];
    int conn_count = 0;
    
    // Parse JSON array manually
    char *ptr = line;
    while (*ptr && *ptr != '[') ptr++; // find first [
    if (*ptr == '[') ptr++;
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            int a = strtol(ptr, &ptr, 10);
            while (*ptr && *ptr != ',' && *ptr != ' ' && *ptr != '\t') ptr++;
            while (*ptr && (*ptr == ',' || *ptr == ' ' || *ptr == '\t')) ptr++;
            int b = strtol(ptr, &ptr, 10);
            
            connections[conn_count][0] = a;
            connections[conn_count][1] = b;
            conn_count++;
            
            // Skip to closing bracket of current pair
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr == ']') ptr++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(n, connections, conn_count));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

BFS visits each node and edge exactly once

⚠ Quadratic 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

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler