Compute distance of each node to a cycle
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
You are given an **undirected** graph with `n` nodes labeled `0..n-1` and a list of edges. The graph is connected and contains **exactly one simple cycle** (i.e., it is a *unicyclic* graph).
For each node `i`, return `dist[i]` = the **minimum number of edges** from node `i` to **any node on the cycle**.
- Nodes that are on the cycle have distance `0`.
### Example (illustrative)
If nodes `{2,3,4}` form the only cycle, then `dist[2]=dist[3]=dist[4]=0`, and nodes in trees attached to the cycle have distance equal to their shortest path length to any of `{2,3,4}`.
### Input / Output
- Input:
- integer `n`
- edges: list of pairs `(u, v)`
- Output: integer array `dist` of length `n`
### Constraints (assume)
- `2 ≤ n ≤ 2 * 10^5`
- `edges.length = n` (connected unicyclic graph)
- `0 ≤ u, v < n`, `u != v`
### Notes
A linear-time approach is expected. (A common approach involves pruning leaves to identify cycle nodes, then multi-source BFS from the cycle.)
Quick Answer: This question evaluates proficiency in graph algorithms, including understanding unicyclic graph structure, cycle identification, and computing minimum distances from nodes to a cycle, and belongs to the Coding & Algorithms domain within graph theory.
Return each node distance to the unique cycle in a connected undirected unicyclic graph.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (5, [[0,1],[1,2],[2,0],[2,3],[3,4]])
Expected Output: [0, 0, 0, 1, 2]
Explanation: Nodes 0,1,2 are on the cycle; tail distances are 1 and 2.
Input: (3, [[0,1],[1,2],[2,0]])
Expected Output: [0, 0, 0]
Explanation: All nodes are on the cycle.
Hints
- Prune leaves to identify cycle nodes.
- Run multi-source BFS from the cycle.