Minimum Edge Reversals So Every Node Is Reachable
Asked at Microsoft, Salesforce, Uber
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.
Asked At
| 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.
Visual walkthrough for a tree with 4 nodes:
Edges: 0->1, 2->1, 0->3 (directed)
Tree rooted at 0: 0->1, 0->3, 2->1 (2->1 is reverse direction)
DFS from 0: node 0 cost = 0
- Node 1: edge 0->1 is original. cost = 0
- Node 3: edge 0->3 is original. cost = 0
- Node 2: path 0->1<-2. Edge 2->1 is reversed. cost = 0 + 1 = 1
Result: [0, 0, 1, 0]
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]
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
from 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.