Minimum Edge Reversals So Every Node Is Reachable

Minimum Edge Reversals So Every Node Is Reachable - Problem

There is a simple directed graph with n nodes labeled from 0 to n - 1. The graph would form a tree if its edges were bi-directional.

You are given an integer n and a 2D integer array edges, where edges[i] = [ui, vi] represents a directed edge going from node ui to node vi.

An edge reversal changes the direction of an edge, i.e., a directed edge going from node ui to node vi becomes a directed edge going from node vi to node ui.

For every node i in the range [0, n - 1], your task is to independently calculate the minimum number of edge reversals required so it is possible to reach any other node starting from node i through a sequence of directed edges.

Return an integer array answer, where answer[i] is the minimum number of edge reversals required so it is possible to reach any other node starting from node i through a sequence of directed edges.

Input & Output

Example 1 — Linear Chain

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

› Output: [3,4,5,4,2,3]

💡 Note: For node 0 as root: need to reverse edges [3,1], [3,2], [5,4] = 3 reversals. For other nodes, use re-rooting to calculate efficiently.

Example 2 — Simple Tree

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

› Output: [0,1,2]

💡 Note: From node 0: no reversals needed. From node 1: reverse [0,1] = 1 reversal. From node 2: reverse [0,1] and [1,2] = 2 reversals.

Example 3 — Star Configuration

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

› Output: [0,1,1,1]

💡 Note: From node 0: all edges point to 0, no reversals needed. From any other node: need 1 reversal to reach node 0, then can reach others.

Constraints

2 ≤ n ≤ 10⁵
edges.length == n - 1
edges[i].length == 2
0 ≤ ui, vi ≤ n - 1
ui != vi
The input is guaranteed to form a tree when edges are bi-directional

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Directed tree with edges that can be reversed

Calculate Reversals

For each node, find minimum reversals to reach all others

Output Array

Return array of minimum reversals for each starting node

Key Takeaway

🎯 Key Insight: Tree re-rooting allows calculating all answers in O(n) time instead of O(n²)

Asked in

G Google 15 f Facebook 8 M Microsoft 12

The key insight is to use tree re-rooting technique. First root the tree at node 0 and calculate initial reversals needed. Then efficiently compute answers for all other nodes by adjusting costs as we re-root. Best approach is tree re-rooting with DFS. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS for Each Node	O(n²)	O(n)	For each node, run DFS to find minimum reversals needed to reach all other nodes
Tree Re-rooting with DFS	O(n)	O(n)	Use tree re-rooting technique to calculate all answers in single pass after initial DFS

Brute Force DFS for Each Node — Algorithm Steps

For each node i from 0 to n-1
Run DFS from node i counting reversals
Sum up all reversals needed for complete reachability

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency list with forward (cost 0) and reverse (cost 1) edges

DFS from Each Node

For each starting node, traverse and count reversal costs

Collect Results

Store reversal count for each starting node

Code -

solution.c — C

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

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

typedef struct {
    Edge* edges;
    int count;
    int capacity;
} AdjList;

int dfs(int node, AdjList* graph, bool* visited) {
    visited[node] = true;
    int totalReversals = 0;
    
    for (int i = 0; i < graph[node].count; i++) {
        int nextNode = graph[node].edges[i].node;
        int cost = graph[node].edges[i].cost;
        
        if (!visited[nextNode]) {
            totalReversals += cost;
            totalReversals += dfs(nextNode, graph, visited);
        }
    }
    
    return totalReversals;
}

int* solution(int n, int** edges, int edgesSize, int* returnSize) {
    *returnSize = n;
    int* result = (int*)malloc(n * sizeof(int));
    
    // Build adjacency list
    AdjList* graph = (AdjList*)malloc(n * sizeof(AdjList));
    for (int i = 0; i < n; i++) {
        graph[i].edges = (Edge*)malloc(2 * edgesSize * sizeof(Edge));
        graph[i].count = 0;
        graph[i].capacity = 2 * edgesSize;
    }
    
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1];
        graph[u].edges[graph[u].count++] = (Edge){v, 0};
        graph[v].edges[graph[v].count++] = (Edge){u, 1};
    }
    
    for (int i = 0; i < n; i++) {
        bool* visited = (bool*)calloc(n, sizeof(bool));
        result[i] = dfs(i, graph, visited);
        free(visited);
    }
    
    // Cleanup
    for (int i = 0; i < n; i++) {
        free(graph[i].edges);
    }
    free(graph);
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char buffer[10000];
    scanf(" %s", buffer);
    
    // Simple parsing for edges
    int** edges = (int**)malloc(n * sizeof(int*));
    int edgesSize = 0;
    
    // Parse edges manually (simplified)
    char* ptr = buffer + 1; // Skip '['
    while (*ptr != ']' && edgesSize < n) {
        if (*ptr == '[') {
            edges[edgesSize] = (int*)malloc(2 * sizeof(int));
            ptr++;
            edges[edgesSize][0] = strtol(ptr, &ptr, 10);
            ptr++; // Skip comma
            edges[edgesSize][1] = strtol(ptr, &ptr, 10);
            edgesSize++;
            while (*ptr != ']') ptr++;
            ptr++;
        }
        ptr++;
    }
    
    int returnSize;
    int* result = solution(n, edges, edgesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    for (int i = 0; i < edgesSize; i++) {
        free(edges[i]);
    }
    free(edges);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of n nodes, we perform DFS traversal of n nodes

⚠ Quadratic Growth

Space Complexity

O(n)

DFS recursion stack and visited array

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~35 min Avg. Time

187 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

Brute Force DFS for Each Node — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler