Problem statement

A directed graph has n nodes numbered 0 to n - 1; each edges[i] = [u, v] is an edge from u to v. If the directions are ignored, the graph is a tree.

An edge reversal turns an edge u → v into v → u.

For every node i, independently, find the minimum number of reversals needed so that every node can be reached from i by following directed edges. Return the answers as an array.

Example 1

Input: n = 4, edges = [[2,0],[2,1],[1,3]]
Output: [1,1,0,2]
Explanation: From node 2 everything is already reachable. From node 0, only 2 → 0 points the wrong way. From node 3, both 1 → 3 and 2 → 1 must flip.

Example 2

Input: n = 3, edges = [[1,2],[2,0]]
Output: [2,0,1]
Explanation: The edges form the chain 1 → 2 → 0, so node 1 needs nothing and node 0 must flip both.

Example 3

Input: n = 2, edges = [[0,1]]
Output: [0,1]

Constraints

• 2 <= n <= 10^5
• edges.length == n - 1
• edges[i].length == 2
• 0 <= u, v < n
• u != v
• the input is a tree when edge directions are ignored

Hints for Minimum Edge Reversals So Every Node Is Reachable

1. Hint 1

   For a fixed root, every edge must point away from it; the answer is the number of edges that point toward the root. One traversal from node 0 computes it for node 0.

2. Hint 2

   Move the root from a node p to a neighbour c. Only the edge between them changes its role — every other edge keeps pointing the same way relative to the root.

3. Hint 3

   If the edge is p → c it was free and now needs flipping (+1); if it is c → p it needed flipping and now is free (−1). Propagate from node 0 outwards (rerooting).

How to solve Minimum Edge Reversals So Every Node Is Reachable

With root r, an edge is fine exactly when it points away from r, so the cost is the count of edges pointing toward r. Moving the root across one edge flips the status of only that edge, so all n answers follow from the first by a single traversal.

Approach

1. Store each edge in both endpoints' lists: (v, 0) at u for the forward direction u → v, and (u, 1) at v for walking against it.
2. Traverse from node 0 and add up the costs of the edges walked: that is ans[0].
3. Traverse again from node 0; for a child c reached through an edge of cost w, set ans[c] = ans[p] + (w == 0 ? 1 : −1).
4. Return ans.

Why it works

For any root, the edges between the root and a node x must all point toward x, and edges elsewhere are judged the same way. When the root moves from p to its neighbour c, every edge other than p–c lies on the same side of both roots and keeps its status; the p–c edge changes from 'must point to c' to 'must point to p', hence the ±1.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Walk the tree undirected — the reversal costs live on the edge entries, not on reachability.
• Use an explicit stack or queue; a recursive DFS can overflow on a path of 10^5 nodes.
• The ±1 depends on the direction of the edge between parent and child, read from the parent's side.

Reference solution

Python

from typing import List

def minEdgeReversals(n: int, edges: List[List[int]]) -> List[int]:
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append((v, 0))
        adj[v].append((u, 1))
    order = [0]
    parent = [-1] * n
    pcost = [0] * n
    seen = [False] * n
    seen[0] = True
    for u in order:
        for v, c in adj[u]:
            if not seen[v]:
                seen[v] = True
                parent[v] = u
                pcost[v] = c
                order.append(v)
    ans = [0] * n
    ans[0] = sum(pcost)
    for v in order[1:]:
        ans[v] = ans[parent[v]] + (1 if pcost[v] == 0 else -1)
    return ans

Java

public static int[] minEdgeReversals(int n, int[][] edges) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) { adj.get(e[0]).add(new int[]{e[1], 0}); adj.get(e[1]).add(new int[]{e[0], 1}); }
    int[] parent = new int[n], pcost = new int[n], order = new int[n];
    boolean[] seen = new boolean[n];
    int head = 0, tail = 0;
    order[tail++] = 0;
    seen[0] = true;
    parent[0] = -1;
    while (head < tail) {
        int u = order[head++];
        for (int[] e : adj.get(u)) {
            if (!seen[e[0]]) { seen[e[0]] = true; parent[e[0]] = u; pcost[e[0]] = e[1]; order[tail++] = e[0]; }
        }
    }
    int[] ans = new int[n];
    for (int c : pcost) ans[0] += c;
    for (int t = 1; t < n; t++) {
        int x = order[t];
        ans[x] = ans[parent[x]] + (pcost[x] == 0 ? 1 : -1);
    }
    return ans;
}

C++

vector<int> minEdgeReversals(int n, vector<vector<int>>& edges) {
    vector<vector<pair<int, int>>> adj(n);
    for (auto& e : edges) { adj[e[0]].push_back({e[1], 0}); adj[e[1]].push_back({e[0], 1}); }
    vector<int> parent(n, -1), pcost(n, 0), order = {0};
    vector<bool> seen(n, false);
    seen[0] = true;
    for (size_t h = 0; h < order.size(); h++) {
        int u = order[h];
        for (auto& e : adj[u]) {
            int v = e.first, c = e.second;
            if (!seen[v]) { seen[v] = true; parent[v] = u; pcost[v] = c; order.push_back(v); }
        }
    }
    vector<int> ans(n, 0);
    for (int c : pcost) ans[0] += c;
    for (int t = 1; t < n; t++) {
        int x = order[t];
        ans[x] = ans[parent[x]] + (pcost[x] == 0 ? 1 : -1);
    }
    return ans;
}

JavaScript

var minEdgeReversals = function(n, edges) {
    var adj = [];
    for (var i = 0; i < n; i++) adj.push([]);
    for (var e = 0; e < edges.length; e++) {
        adj[edges[e][0]].push(edges[e][1], 0);
        adj[edges[e][1]].push(edges[e][0], 1);
    }
    var parent = [], pcost = [], seen = [], order = [0];
    for (var j = 0; j < n; j++) { parent.push(-1); pcost.push(0); seen.push(false); }
    seen[0] = true;
    for (var h = 0; h < order.length; h++) {
        var u = order[h];
        for (var k = 0; k < adj[u].length; k += 2) {
            var v = adj[u][k];
            if (!seen[v]) { seen[v] = true; parent[v] = u; pcost[v] = adj[u][k + 1]; order.push(v); }
        }
    }
    var ans = new Array(n);
    ans[0] = 0;
    for (var a = 0; a < n; a++) ans[0] += pcost[a];
    for (var t = 1; t < n; t++) {
        var x = order[t];
        ans[x] = ans[parent[x]] + (pcost[x] === 0 ? 1 : -1);
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Maximum Sum BST in Binary Tree Hard
• Binary Tree Cameras Hard
• Binary Tree Maximum Path Sum Hard
• Maximum Product of the Length of Two Palindromic Substrings Hard
• Longest Chunked Palindrome Decomposition Hard
• Time Taken to Mark All Nodes Hard