Minimum Edge Reversals So Every Node Is Reachable

Hard Graphs Re-rooting DP Original on LeetCode

Minimum Edge Reversals So Every Node Is Reachable is a hard graphs problem solved with the re-rooting dp pattern. The best approach, optimal (re-rooting in two passes), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (one bfs per start node) up.

Problem

You are given a directed graph with n nodes labelled 0 to n - 1 and n - 1 edges, where edges[i] = [u, v] is an edge from u to v. If the directions are ignored, the edges form a tree.

Reversing an edge turns u → v into v → u. For every node i, find the minimum number of reversals needed so that, starting at i, you can reach every other node by following directed edges. Each node’s answer is computed on its own (reversals do not carry over between nodes).

Return an array answer where answer[i] is that minimum for node i.

Examples

Example 1

Input
n = 4, edges = [[1,0],[1,2],[3,2]]
Output
[2,1,2,1]
Why
From node 1, only 3→2 points the wrong way, so one reversal is enough. From node 0, both 1→0 and 3→2 must flip.

Example 2

Input
n = 3, edges = [[0,1],[0,2]]
Output
[0,1,1]
Why
Node 0 already reaches everything. Starting at 1 (or 2) you must flip the edge that points into it.

Example 3

Input
n = 2, edges = [[1,0]]
Output
[1,0]
Why
Node 1 reaches 0 directly; node 0 needs the single edge flipped.

Constraints

  • 2 <= n <= 10^5
  • edges.length == n - 1, edges[i] = [u, v] is a directed edge from u to v, 0 <= u, v < n, u != v
  • Ignoring directions, the edges form a tree (connected, no cycles).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (one BFS per start node)O(n²)O(n)
Optimal (re-rooting in two passes)O(n)O(n)

1Brute force (one BFS per start node)

TimeO(n²)n breadth-first searches, each touching all n nodes and n - 1 edges.
SpaceO(n)Adjacency list, queue and visited array (reused per start).

Build an undirected adjacency list where each entry remembers whether walking it agrees with the original edge (cost 0) or goes against it (cost 1). For every start node, BFS over the tree and add up the costs of the edges used.

  1. For each edge u → v: add (v, 0) to adj[u] and (u, 1) to adj[v].
  2. For each s: BFS from s with a visited array; whenever you go from x to an unvisited y with cost w, add w to answer[s].
class Solution {
    public 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[] answer = new int[n];
        for (int s = 0; s < n; s++) {
            boolean[] seen = new boolean[n];
            ArrayDeque<Integer> queue = new ArrayDeque<>();
            queue.add(s);
            seen[s] = true;
            int cost = 0;
            while (!queue.isEmpty()) {
                int x = queue.poll();
                for (int[] next : adj.get(x)) {
                    if (!seen[next[0]]) {
                        seen[next[0]] = true;
                        cost += next[1];
                        queue.add(next[0]);
                    }
                }
            }
            answer[s] = cost;
        }
        return answer;
    }
}

2Optimal (re-rooting in two passes)

TimeO(n)Two linear passes over a tree with n - 1 edges.
SpaceO(n)Adjacency list plus order, parent-cost and answer arrays.

Root the tree at node 0 and compute its answer with one BFS (sum of costs walking away from 0). Then re-root: moving the start from a parent u to its child v flips only the edge between them. If walking u → v cost 0 (the edge points down), it now costs 1 to walk back up, so answer[v] = answer[u] + 1; if it cost 1, answer[v] = answer[u] - 1. Process children in BFS order so the parent is always done first. Both passes are iterative, so deep trees are safe.

  1. Build the same weighted undirected adjacency list.
  2. BFS from 0, recording the visiting order, each node's parent, and the cost w of the edge used to reach it. answer[0] = sum of those costs.
  3. For each node v in BFS order (except 0), with parent u and cost w: answer[v] = answer[u] + (w == 0 ? 1 : -1).
class Solution {
    public 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[] order = new int[n], parent = new int[n], upCost = new int[n];
        boolean[] seen = new boolean[n];
        order[0] = 0;
        seen[0] = true;
        parent[0] = -1;
        int head = 0, tail = 1, rootCost = 0;
        while (head < tail) {
            int x = order[head++];
            for (int[] next : adj.get(x)) {
                int y = next[0];
                if (!seen[y]) {
                    seen[y] = true;
                    parent[y] = x;
                    upCost[y] = next[1];
                    rootCost += next[1];
                    order[tail++] = y;
                }
            }
        }
        int[] answer = new int[n];
        answer[0] = rootCost;
        for (int k = 1; k < n; k++) {
            int v = order[k];
            answer[v] = answer[parent[v]] + (upCost[v] == 0 ? 1 : -1);
        }
        return answer;
    }
}

Edge cases to test

  • Two nodes
  • A star where every edge points into the centre, or every edge points out
  • A long path whose edges alternate direction
  • A deep tree (a path of 10^5 nodes), which breaks naive recursion

Hints

Hint 1

Treat the tree as undirected, but give each edge a cost: 0 when you walk along its direction, 1 when you walk against it. The answer for a start node is the total cost of walking out from it to every other node.

Hint 2

Computing that for one node is a single BFS. Doing it for all n nodes is O(n²): too slow.

Hint 3

Move the start from a node u to its neighbour v. Only the edge between them changes direction relative to the start: if it pointed u → v, the answer grows by 1; if it pointed v → u, it shrinks by 1.

FAQ

What is the best time complexity for Minimum Edge Reversals So Every Node Is Reachable?

Optimal (re-rooting in two passes) runs in O(n) time and O(n) extra space. Two linear passes over a tree with n - 1 edges.

Which pattern does Minimum Edge Reversals So Every Node Is Reachable use?

It is a graphs problem that uses the re-rooting dp pattern. Other problems with the same pattern: Sum of Distances in Tree.

Is there a brute force solution for Minimum Edge Reversals So Every Node Is Reachable?

Yes. Brute force (one BFS per start node) takes O(n²) time and O(n) space. Build an undirected adjacency list where each entry remembers whether walking it agrees with the original edge (cost 0) or goes against it (cost 1).

Which edge cases should I test for Minimum Edge Reversals So Every Node Is Reachable?

Two nodes; A star where every edge points into the centre, or every edge points out; A long path whose edges alternate direction; A deep tree (a path of 10^5 nodes), which breaks naive recursion.