2858. Minimum Edge Reversals So Every Node Is Reachable
Asked at Microsoft, Salesforce, Uber
Difficulty
Hard
Time
O(n)
Space
O(n)
Pattern
Dynamic Programming
Companies
3
Problem
You are given n nodes labeled 0 to n - 1 and a list of directed edges. If you ignore the directions, these edges form a tree: there are exactly n - 1 edges and no cycles.
For each node i, you must answer this question independently: what is the smallest number of edges you must flip so that, starting at i, you can walk along directed edges and reach every other node? Flipping an edge u -> v turns it into v -> u.
Return an array answer of length n, where answer[i] is that minimum count for node i. Note that each node's answer is computed on its own — the flips you make for one node do not carry over to the next.
Directed edges that form a tree
Constraints
- ●
2 <= n <= 10^5 - ●
edges.length == n - 1 - ●
edges[i].length == 2 - ●
0 <= ui == edges[i][0] < n - ●
0 <= vi == edges[i][1] < n - ●
ui != vi - ●
If the edges were bi-directional, the graph would be a tree.
Examples
n = 4, edges = [[2,0],[2,1],[1,3]][1,1,0,2]n = 3, edges = [[1,2],[2,0]][2,0,1]Asked At
3 companies| Company | Difficulty | |
|---|---|---|
| Microsoft | Hard | View all Microsoft questions → |
| Salesforce | Hard | View all Salesforce questions → |
| Uber | Hard | View all Uber questions → |
How to Think About It
Key insight: build the graph with original edges (weight 0) and reversed edges (weight 1). For each node, the cost to reach it from node 0 is the minimum number of reversals needed on some path. This becomes a shortest path problem with 0/1 weights.
0/1 BFS: since edge weights are 0 or 1, use a deque for BFS. Push nodes reached via original edges to the front (cost 0), and nodes reached via reversed edges to the back (cost 1). This gives O(V+E) time.
Re-rooting DP (for tree variant): root the tree at node 0. For each edge (parent, child): if the edge is original (parent->child), the child inherits the parent's cost. If reversed (child->parent), the child gets parent's cost + 1. Then re-root to compute costs for all nodes.
Complexity: O(V+E) time and O(V+E) space for both 0/1 BFS and tree DP approaches.
Optimal Approach
Build an augmented graph: for each original edge u->v, add edge u->v with weight 0 (no reversal needed) and edge v->u with weight 1 (reversal needed). Run 0/1 BFS from node 0 using a deque. Push neighbors reached via weight-0 edges to the front, and weight-1 edges to the back. The distance array gives the minimum reversals to reach each node.
Walkthrough with edges 0->1, 2->1, 0->3:
- Augmented graph: 0->1(w=0), 1->0(w=1), 2->1(w=0), 1->2(w=1), 0->3(w=0), 3->0(w=1)
- BFS from 0: deque=[(0,0)]. distances=[0,-1,-1,-1]
- Process 0: push 1(w=0) front, 3(w=0) front. deque=[(1,0),(3,0)]. distances=[0,0,-1,0]
- Process 1: push 0(w=1) back, 2(w=1) back. deque=[(3,0),(0,1),(2,1)]. distances=[0,0,1,0]
- Process 3: push 0(w=1) back. deque=[(0,1),(2,1),(0,1)]. distances unchanged.
- Process 0: already visited. Process 2: push 1(w=0) front. deque=[(1,0)]. distances=[0,0,1,0]
- Result: [0, 0, 1, 0]
0/1 BFS on the augmented graph
What Trips People Up in Real Interviews
Assuming the graph is a tree. This problem works on general directed graphs. For trees, the DP approach is simpler. For general graphs, use 0/1 BFS or Dijkstra with 0/1 weights.
Forgetting that node 0 is always reachable with 0 reversals. Start BFS/DFS from node 0 with cost 0.
Confusing "edge reversal" with "edge addition." Reversal means flipping an existing directed edge, not adding new edges.
Not handling disconnected components. If some node is unreachable even after all reversals, the problem constraints guarantee this is possible. But clarify with the interviewer.
Using regular BFS instead of 0/1 BFS. Regular BFS treats all edges as weight 1, which gives wrong answers when some edges have weight 0. Use deque-based BFS for 0/1 weights.
Solution Code
O(n) timefrom collections import deque
def minReversals(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append((v, 0))
graph[v].append((u, 1))
dist = [-1] * n
dist[0] = 0
dq = deque([0])
while dq:
node = dq.popleft()
for neighbor, weight in graph[node]:
if dist[neighbor] == -1:
dist[neighbor] = dist[node] + weight
if weight == 0:
dq.appendleft(neighbor)
else:
dq.append(neighbor)
return distFrequently Asked Questions
What is the Minimum Edge Reversals So Every Node Is Reachable problem?
Given a directed graph with n nodes and edges, find the minimum number of edge reversals needed so that every node is reachable from node 0. This problem combines tree DP, BFS/DFS traversal, and graph re-rooting techniques.
How do you solve Minimum Edge Reversals So Every Node Is Reachable?
The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Minimum Edge Reversals So Every Node Is Reachable?
Minimum Edge Reversals So Every Node Is Reachable is asked at Microsoft, Salesforce, Uber. It is a hard difficulty problem.
What are common mistakes on Minimum Edge Reversals So Every Node Is Reachable?
- Assuming the graph is a tree. This problem works on general directed graphs. For trees, the DP approach is simpler. For general graphs, use 0/1 BFS or Dijkstra with 0/1 weights.
- Forgetting that node 0 is always reachable with 0 reversals. Start BFS/DFS from node 0 with cost 0.
- Confusing "edge reversal" with "edge addition." Reversal means flipping an existing directed edge, not adding new edges.
- Not handling disconnected components. If some node is unreachable even after all reversals, the problem constraints guarantee this is possible. But clarify with the interviewer.
- Using regular BFS instead of 0/1 BFS. Regular BFS treats all edges as weight 1, which gives wrong answers when some edges have weight 0. Use deque-based BFS for 0/1 weights.