Distances to Cycles
Belvedere Trading● MediumFULLTIMEOAProblem statement
You are given an undirected graph with vertices 0 through n - 1. Every connected component contains exactly one simple cycle.
For each vertex, return the minimum number of edges needed to reach any vertex on the unique cycle in its connected component. A vertex on a cycle has distance 0.
Function
distancesToCycles(n: int, edges: int[][]) → int[]Examples
Example 1
n = 6edges = [[0,1],[1,2],[2,0],[2,3],[3,4],[4,5]]return = [0,0,0,1,2,3]Vertices 0, 1, and 2 form the cycle. Vertices 3, 4, and 5 are respectively one, two, and three edges from it.
Example 2
n = 7edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,3],[5,6]]return = [0,0,0,0,0,0,1]The graph has two components. Vertices 0, 1, 2 and vertices 3, 4, 5 are on cycles; vertex 6 is one edge from the second cycle.
Constraints
3 <= n <= 2 * 10^5.edges.length = n.- Each edge contains two distinct vertices in
[0, n - 1]. - The graph has no duplicate edges.
- Every connected component contains exactly one simple cycle.