Distance from Every Vertex to the Only Cycle
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
A connected, simple undirected graph has vertices numbered from `0` through `n - 1` and contains exactly one cycle. Return an array of length `n` whose entry for vertex `i` is the minimum number of edges needed to reach any vertex on that cycle. A cycle vertex has distance zero.
```cpp
class Solution {
public:
vector<int> distanceToCycle(int n, vector<vector<int>>& edges);
};
```
### Examples
**Example 1:**
```text
n = 4, edges = [[0,1],[1,2],[2,0],[2,3]]
Output: [0,0,0,1]
Explanation: Vertices 0,1,2 form the cycle and 3 attaches to 2.
```
**Example 2:**
```text
n = 5, edges = [[0,1],[1,2],[2,0],[0,3],[3,4]]
Output: [0,0,0,1,2]
Explanation: The attached chain has distances one and two.
```
### Constraints
- `3 <= n <= 10^5`; `edges.length == n`.
- Edges have distinct valid endpoints in `[0,n-1]`; no repeated vertex pair.
- The graph is connected and has exactly one cycle.
### Clarifying Questions
Distance counts edges to the nearest cycle vertex, not to a fixed numbered vertex.
```hint Inspect the structure
What remains after repeatedly deleting all degree-one vertices?
```
### Reasoning checkpoints
- Measure distance to the nearest cycle vertex rather than to a fixed chosen vertex.
- Use the connected, exactly-one-cycle guarantee correctly and account for every labeled vertex.
- Justify that all returned distances are shortest, including vertices deep in attached branches.
### Optional extensions
Which parts of your reasoning would need reconsideration if the graph could contain several cycles?
Overview: Distance from Every Vertex to the Only Cycle. The simple undirected graph has n labeled vertices, is connected, and contains exactly one cycle. Return an n-entry array whose i-th value is the minimum number of edges from i to any cycle vertex. A vertex on the cycle has distance zero.