Find Each Node’s Minimum Reversals to Reach the Whole Tree
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Find Each Node’s Minimum Reversals to Reach the Whole Tree
A simple directed graph has `n` nodes labeled from `0` through `n - 1`. If its edges were made bidirectional, the graph would be a tree.
Each entry `[u,v]` in `edges` is an edge directed from `u` to `v`. Reversing an edge changes `u -> v` to `v -> u`.
For each node `i`, independently find the minimum number of edge reversals needed so that a path of directed edges can reach every other node starting at `i`. Return an array `answer` in node-label order, where `answer[i]` contains that minimum.
### Examples
**Example 1**
```text
Input: n = 4, edges = [[0,1],[2,1],[2,3]]
Output: [1,2,1,2]
```
From node `0`, reverse `2 -> 1`. From node `1`, reverse both `0 -> 1` and `2 -> 1`. From node `2`, reverse only `0 -> 1`. From node `3`, reverse `2 -> 3` and `0 -> 1`. Each case starts with the original edge directions.
**Example 2**
```text
Input: n = 3, edges = [[0,2],[1,2]]
Output: [1,1,2]
```
Starting from `0` requires reversing `1 -> 2`; starting from `1` requires reversing `0 -> 2`. Starting from `2` requires reversing both edges.
### Constraints
- `2 <= n <= 10^5`.
- `edges.length == n - 1`.
- `edges[i].length == 2`.
- `0 <= u_i == edges[i][0] < n`.
- `0 <= v_i == edges[i][1] < n`.
- `u_i != v_i`.
- The graph becomes a tree if every edge is made bidirectional.
### Clarifying Questions
- Do reversals for one starting node carry into the next case? No; each answer is computed independently from the original graph.
- Must other nodes reach the chosen node? The requirement is the opposite: the chosen node must reach every other node.
- Is one common set of reversals required to work for all roots? No; each node may require its own reversal set.
- Can the returned array be reordered? No; entry `i` corresponds to node label `i`.
### C++ Interface
```cpp
class Solution {
public:
vector<int> minEdgeReversals(int n, vector<vector<int>>& edges) {
}
};
```
### Reasoning Checkpoints
- Use the tree guarantee while respecting each original edge direction.
- Derive each node’s answer from the original graph, without accumulating physical reversals.
- Support a tree that is a chain at the maximum input size.
```hint Neighboring starting nodes
Compare the required edge directions when the starting node moves across one tree edge. Which direction requirements elsewhere in the tree change?
```
Overview: For every starting node independently, find the fewest original tree-edge directions to reverse so that the node can reach every other node.