Watch 10 video solutions for Minimum Edge Reversals So Every Node Is Reachable, a hard level problem involving Dynamic Programming, Depth-First Search, Breadth-First Search. This walkthrough by Aryan Mittal has 6,558 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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:
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 <= 105edges.length == n - 1edges[i].length == 20 <= ui == edges[i][0] < n0 <= vi == edges[i][1] < nui != viProblem Overview: You are given a directed tree with n nodes. For each node, determine the minimum number of edge reversals required so every other node becomes reachable starting from that node. The output is an array where index i represents the minimum reversals needed if node i is treated as the root.
Approach 1: Reverse BFS Traversal (O(n) time, O(n) space)
Model each edge in both directions inside an adjacency list. The original direction has cost 0 and the reversed direction has cost 1. Run a Breadth-First Search from node 0 to count how many edges must be reversed so every node becomes reachable from this root. Each traversal accumulates the reversal cost based on edge direction. This produces the baseline number of reversals for node 0. The insight is that moving along an edge aligned with the direction requires no change, while going against it implies a reversal.
Approach 2: BFS Re-rooting Propagation (O(n) time, O(n) space)
After computing the reversal count for root 0, propagate results to all nodes using another BFS. When moving the root from node u to neighbor v, adjust the answer depending on edge orientation. If the original edge is u → v, re-rooting requires one extra reversal. If it is v → u, one reversal is saved. This local adjustment allows computing results for all nodes without recomputing the whole traversal. The graph is processed once, making it linear time.
Approach 3: Using BFS to Determine Minimum Edge Reversals from Root (O(n) time, O(n) space)
This variation focuses on computing the base cost from a single root using weighted traversal logic. Each edge contributes either 0 or 1 depending on whether it must be reversed relative to traversal direction. The algorithm iterates through neighbors and accumulates reversal costs while marking visited nodes. This approach isolates the core counting step and is useful before applying a re-rooting optimization.
Approach 4: Dynamic Programming with Tree Re-rooting (O(n) time, O(n) space)
Use Depth-First Search combined with a re-rooting technique often used in dynamic programming on trees. The first DFS calculates how many reversals are needed when node 0 is the root. A second DFS propagates results to children by adjusting counts depending on edge orientation. Re-rooting avoids recomputation by reusing parent results and modifying them with constant-time updates. This technique generalizes well to many tree DP problems where answers depend on the chosen root.
Recommended for interviews: The tree re-rooting dynamic programming approach is the expected optimal solution. It runs in linear time and demonstrates strong understanding of graph traversal and root transition logic. Starting with the BFS counting step helps clarify the problem, but implementing the re-rooting propagation shows deeper algorithmic skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse BFS Traversal | O(n) | O(n) | Compute base reversal count from a single root |
| BFS Re-rooting Propagation | O(n) | O(n) | Efficiently derive answers for all nodes after initial root computation |
| BFS Root Cost Calculation | O(n) | O(n) | Understanding the core reversal counting logic |
| Dynamic Programming with DFS (Tree Re-rooting) | O(n) | O(n) | Interview‑optimal solution for computing results for every node |