# Minimum Edge Reversals So Every Node Is Reachable
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-edge-reversals-so-every-node-is-reachable)
Canonical: https://scaleengineer.com/dsa/problems/minimum-edge-reversals-so-every-node-is-reachable
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Graph
**Companies:** [MathWorks](https://scaleengineer.com/companies/mathworks)
---
## 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**._

**Example 1:**

![](https://assets.glich.co/dsa/minimum-edge-reversals-so-every-node-is-reachable/image0.png)

**Input:** n = 4, edges = [[2,0],[2,1],[1,3]]
**Output:** [1,1,0,2]
**Explanation:** The image above shows the graph formed by the edges.
For node 0: after reversing the edge [2,0], it is possible to reach any other node starting from node 0.
So, answer[0] = 1.
For node 1: after reversing the edge [2,1], it is possible to reach any other node starting from node 1.
So, answer[1] = 1.
For node 2: it is already possible to reach any other node starting from node 2.
So, answer[2] = 0.
For node 3: after reversing the edges [1,3] and [2,1], it is possible to reach any other node starting from node 3.
So, answer[3] = 2.

**Example 2:**

![](https://assets.glich.co/dsa/minimum-edge-reversals-so-every-node-is-reachable/image1.png)

**Input:** n = 3, edges = [[1,2],[2,0]]
**Output:** [2,0,1]
**Explanation:** The image above shows the graph formed by the edges.
For node 0: after reversing the edges [2,0] and [1,2], it is possible to reach any other node starting from node 0.
So, answer[0] = 2.
For node 1: it is already possible to reach any other node starting from node 1.
So, answer[1] = 0.
For node 2: after reversing the edge [1, 2], it is possible to reach any other node starting from node 2.
So, answer[2] = 1.

**Constraints:**

* `2 <= n <= 105`
* `edges.length == n - 1`
* `edges[i].length == 2`
* `0 <= ui == edges[i][0] < n`
* `0 <= vi == edges[i][1] < n`
* `ui != vi`
* The input is generated such that if the edges were bi-directional, the graph would be a tree.

# Approaches
## Brute Force with Traversal for Each Node
This approach iterates through each node from `0` to `n-1`, treating each one as a potential root. For each potential root, it calculates the minimum number of edge reversals required to make all other nodes reachable.
**Time:** O(N^2). For each of the `N` nodes, we perform a full graph traversal (BFS/DFS), which takes `O(N + E)` time. Since `E = N-1`, this is `O(N)`. Repeating this `N` times gives `O(N^2)`. · **Space:** O(N). We need `O(N)` space for the adjacency list, `O(N)` for the `HashSet` of edges, and `O(N)` for the BFS queue and `visited` array.
**Pros:** Simple to understand and implement.; Correctly solves the problem by simulating the process for each node.
**Cons:** Inefficient due to re-computation. The `O(N^2)` time complexity is too slow for the given constraints (`n <= 10^5`).
### Explanation
To make all nodes reachable from a starting node `i`, the graph must form a directed tree rooted at `i`, where all edges point away from the root. The underlying undirected graph is a tree, so there's a unique path from `i` to any other node `j`. We need to ensure all edges on these paths are directed away from `i`.

The algorithm for each potential root `i` is as follows:
1.  Initialize a counter for reversals to zero.
2.  Perform a graph traversal (like BFS or DFS) starting from `i` on the underlying undirected graph structure.
3.  To do this, we first build an undirected adjacency list from the given directed edges. We also need a way to check the original direction of an edge, for example, by storing the directed edges in a `HashSet` of pairs.
4.  During the traversal, whenever we move from a node `u` to a neighbor `v`, we check the original direction of the edge between them.
5.  If the original edge was `v -> u`, it's pointing towards the root `i` instead of away from it. This edge must be reversed, so we increment the reversal counter.
6.  After the traversal completes, the counter holds the total number of reversals needed for `i` to be the root. This value is stored in `answer[i]`.
7.  This process is repeated for all `n` nodes.

```java
import java.util.*;

class Solution {
    public int[] minEdgeReversals(int n, int[][] edges) {
        // Store original directed edges for quick lookup
        Set<String> originalEdges = new HashSet<>();
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            originalEdges.add(u + "," + v);
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = countReversalsForRoot(i, n, adj, originalEdges);
        }
        return answer;
    }

    private int countReversalsForRoot(int root, int n, List<List<Integer>> adj, Set<String> originalEdges) {
        int reversals = 0;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];

        queue.offer(root);
        visited[root] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    // We are traversing from u to v.
                    // The edge should be u -> v.
                    // If the original edge is v -> u, we need a reversal.
                    if (originalEdges.contains(v + "," + u)) {
                        reversals++;
                    }
                    queue.offer(v);
                }
            }
        }
        return reversals;
    }
}
```
### Algorithm
*   Create an adjacency list for the undirected version of the graph.
*   Store the original directed edges in a `HashSet` for efficient lookups.
*   Iterate through each node `i` from `0` to `n-1`.
    *   For each `i`, perform a Breadth-First Search (BFS) or Depth-First Search (DFS) starting from `i`.
    *   Initialize a `reversals` count to 0.
    *   During the traversal from a node `u` to a neighbor `v`, check if the original edge was `v -> u`.
    *   If it was, increment the `reversals` count.
    *   After the traversal is complete, store the total `reversals` in `answer[i]`.
*   Return the `answer` array.

## Two-Pass DFS with Rerooting Technique
This approach avoids redundant calculations by using a dynamic programming technique on the tree, often called "rerooting". It consists of two main passes (DFS traversals). The first pass calculates the answer for an arbitrary root (e.g., node 0). The second pass uses this result to efficiently compute the answers for all other nodes in linear time.
**Time:** O(N). Building the adjacency list takes `O(N)` time. Both DFS traversals visit each node and edge once, taking `O(N + E)` time, which is `O(N)` as `E = N-1`. · **Space:** O(N). The adjacency list requires `O(N)` space. The recursion stack for DFS can go up to `O(N)` in the worst case (a linear tree). The `answer` array also takes `O(N)` space.
**Pros:** Highly efficient with linear time complexity, making it suitable for large inputs.; Elegantly solves the problem by reusing previously computed results.
**Cons:** The logic, especially the rerooting step, can be less intuitive to grasp compared to the brute-force method.
### Explanation
The core idea is that the answers for adjacent nodes are closely related. If we know the number of reversals for a node `u` to be the root, we can calculate the answer for its neighbor `v` with a simple update.

**First Pass (DFS from an arbitrary root):**
1.  We start by choosing an arbitrary root, say node `0`.
2.  We build an adjacency list that represents the undirected tree structure but also encodes the original edge directions. For each original edge `u -> v`, we can add `(v, 0)` to `u`'s adjacency list and `(u, 1)` to `v`'s list. The second element in the pair represents the cost of traversal: `0` for following the original direction and `1` for going against it (a reversal).
3.  We perform a post-order DFS traversal (`dfs1`) starting from the root `0`. This traversal calculates `answer[0]`, the number of reversals needed to make `0` the universal source. During the traversal from a parent `u` to a child `v`, if the edge `u -> v` is against the original direction (cost is 1), we add 1 to our total count.

**Second Pass (Rerooting DFS):**
1.  Now, we perform a second, pre-order DFS traversal (`dfs2`) starting from root `0` to calculate the answers for all other nodes.
2.  When we move from a parent `u` to a child `v`, we can compute `answer[v]` based on `answer[u]`.
3.  When the root shifts from `u` to `v`, the required direction of the edge between them flips.
    *   If the original edge was `u -> v`, it was correctly oriented for root `u` (cost 0), but needs to be reversed for root `v` (cost 1). So, `answer[v]` will be one more than `answer[u]` would be, considering only this edge's change.
    *   If the original edge was `v -> u`, it was incorrectly oriented for root `u` (cost 1), but is now correctly oriented for root `v` (cost 0). So, `answer[v]` will be one less.
4.  The formula is: `answer[v] = answer[u] + (original edge u->v ? 1 : -1)`.
5.  We apply this formula recursively down the tree.

```java
import java.util.*;

class Solution {
    List<List<int[]>> adj;
    int[] answer;

    public int[] minEdgeReversals(int n, int[][] edges) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            // u -> v: cost 0 from u to v, cost 1 from v to u
            adj.get(u).add(new int[]{v, 0});
            adj.get(v).add(new int[]{u, 1});
        }

        answer = new int[n];
        
        // First DFS to calculate answer for root 0
        dfs1(0, -1);
        
        // Second DFS to calculate answers for all other nodes
        dfs2(0, -1);
        
        return answer;
    }

    // DFS to calculate the cost for the tree rooted at 0.
    private void dfs1(int u, int p) {
        for (int[] edgeInfo : adj.get(u)) {
            int v = edgeInfo[0];
            int cost = edgeInfo[1];
            if (v == p) continue;
            answer[0] += cost; // cost is 1 if edge is v->u, needs reversal for u->v
            dfs1(v, u);
        }
    }

    // DFS to compute answers for all nodes based on the parent's answer
    private void dfs2(int u, int p) {
        for (int[] edgeInfo : adj.get(u)) {
            int v = edgeInfo[0];
            int cost = edgeInfo[1];
            if (v == p) continue;
            
            // When moving root from u to v:
            // If original edge was u->v (cost=0), we need to reverse it. Cost increases by 1.
            // If original edge was v->u (cost=1), it's now in the correct direction. Cost decreases by 1.
            // The change is 1 - 2*cost. If cost=0, change=1. If cost=1, change=-1.
            answer[v] = answer[u] + (1 - 2 * cost);
            dfs2(v, u);
        }
    }
}
```
### Algorithm
*   Build an adjacency list for the graph. For each directed edge `u -> v`, add `v` to `u`'s neighbors with a `cost` of 0, and add `u` to `v`'s neighbors with a `cost` of 1 (indicating a reversal is needed to traverse `v -> u`).
*   Initialize an `answer` array of size `n`.
*   **First Pass (DFS):**
    *   Perform a DFS from an arbitrary root (e.g., node 0).
    *   This DFS (`dfs1`) calculates the total reversals needed if node 0 is the root.
    *   In `dfs1(u, parent)`, for each child `v` of `u`, add the cost of the `u -> v` traversal to `answer[0]`. Then, recurse on the child.
*   **Second Pass (DFS):**
    *   Perform another DFS from the same root (node 0).
    *   This DFS (`dfs2`) calculates the answer for each node based on its parent's answer.
    *   In `dfs2(u, parent)`, for each child `v` of `u`:
        *   The answer for `v` is derived from the answer for `u`. When the root moves from `u` to `v`, the cost associated with the edge `(u, v)` flips.
        *   If the original edge was `u -> v`, `answer[v] = answer[u] + 1`.
        *   If the original edge was `v -> u`, `answer[v] = answer[u] - 1`.
        *   Recursively call `dfs2(v, u)`.
*   Return the `answer` array.

# Solutions
### Java

```java
class Solution {
private
  List<int[]>[] g;
private
  int[] ans;
public
  int[] minEdgeReversals(int n, int[][] edges) {
    ans = new int[n];
    g = new List[n];
    Arrays.setAll(g, i->new ArrayList<>());
    for (var e : edges) {
      int x = e[0], y = e[1];
      g[x].add(new int[]{y, 1});
      g[y].add(new int[]{x, -1});
    }
    dfs(0, -1);
    dfs2(0, -1);
    return ans;
  }
private
  void dfs(int i, int fa) {
    for (var ne : g[i]) {
      int j = ne[0], k = ne[1];
      if (j != fa) {
        ans[0] += k < 0 ? 1 : 0;
        dfs(j, i);
      }
    }
  }
private
  void dfs2(int i, int fa) {
    for (var ne : g[i]) {
      int j = ne[0], k = ne[1];
      if (j != fa) {
        ans[j] = ans[i] + k;
        dfs2(j, i);
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> minEdgeReversals(int n, vector<vector<int>> &edges) {
    vector<pair<int, int>> g[n];
    vector<int> ans(n);
    for (auto &e : edges) {
      int x = e[0], y = e[1];
      g[x].emplace_back(y, 1);
      g[y].emplace_back(x, -1);
    }
    function<void(int, int)> dfs = [&](int i, int fa) {
      for (auto &[j, k] : g[i]) {
        if (j != fa) {
          ans[0] += k < 0;
          dfs(j, i);
        }
      }
    };
    function<void(int, int)> dfs2 = [&](int i, int fa) {
      for (auto &[j, k] : g[i]) {
        if (j != fa) {
          ans[j] = ans[i] + k;
          dfs2(j, i);
        }
      }
    };
    dfs(0, -1);
    dfs2(0, -1);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]: ans = [0] * n g = [[] for _ in range(n)] for x, y in edges: g[x]. append((y, 1)) g[y]. append((x, - 1)) def dfs(i: int, fa: int): for j, k in g[i]: if j != fa: ans[0] += int(k < 0) dfs(j, i) dfs(0, - 1) def dfs2(i: int, fa: int): for j, k in g[i]: if j != fa: ans[j] = ans[i] + k dfs2(j, i) dfs2(0, - 1) return ans

```