You are given a positive integer n representing the number of nodes in a
connected undirected graph containing exactly one cycle. The nodes are numbered from 0 to n - 1 (inclusive).
You are also given a 2D integer array edges, where edges[i] = [node1i, node2i] denotes that there is a bidirectional edge connecting node1i
and node2i in the graph.
The distance between two nodes a and b is defined to be the minimum number of edges that are needed to go from a to b.
Return an integer arrayanswerof sizen, whereanswer[i]_is theminimum distance between the _ithnode andany node in the cycle.

Input: n =7, edges =[[1,2],[2,4],[4,3],[3,1],[0,1],[5,2],[6,5]]Output: [1,0,0,0,0,1,2]Explanation:
The nodes 1,2,3, and 4 form the cycle.The distance from 0 to 1is1.The distance from 1 to 1is0.The distance from 2 to 2is0.The distance from 3 to 3is0.The distance from 4 to 4is0.The distance from 5 to 2is1.The distance from 6 to 2is2.
Example 2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14

Input: n =9, edges =[[0,1],[1,2],[0,2],[2,6],[6,7],[6,8],[0,3],[3,4],[3,5]]Output: [0,0,0,1,2,2,1,2,2]Explanation:
The nodes 0,1, and 2 form the cycle.The distance from 0 to 0is0.The distance from 1 to 1is0.The distance from 2 to 2is0.The distance from 3 to 1is1.The distance from 4 to 1is2.The distance from 5 to 1is2.The distance from 6 to 2is1.The distance from 7 to 2is2.The distance from 8 to 2is2.
Constraints:
3 <= n <= 10^5
edges.length == n
edges[i].length == 2
0 <= node1i, node2i <= n - 1
node1i != node2i
The graph is connected.
The graph has exactly one cycle.
There is at most one edge between any pair of vertices.
The graph has exactly one cycle. If we can find all nodes in the cycle, then for every node, the minimum distance to the cycle is the shortest path to any node in the cycle. We can use DFS to find the cycle, then BFS from all cycle nodes to compute distances.
classSolution {
fundistanceToCycle(n: Int, edges: Array<IntArray>): IntArray {
val g = Array(n) { mutableListOf<Int>() }
for (e in edges) {
g[e[0]].add(e[1])
g[e[1]].add(e[0])
}
val inCycle = BooleanArray(n)
val parent = IntArray(n) { -1 }
var start = -1var end = -1fundfs(u: Int, p: Int): Boolean {
parent[u] = p
for (v in g[u]) {
if (v == p) continueif (parent[v] == -1) {
if (dfs(v, u)) returntrue } else {
start = v; end = u
returntrue }
}
returnfalse }
dfs(0, -1)
var x = end
while (x != start) {
inCycle[x] = true x = parent[x]
}
inCycle[start] = trueval ans = IntArray(n) { -1 }
val q = ArrayDeque<Int>()
for (i in0 until n) {
if (inCycle[i]) {
ans[i] = 0 q.add(i)
}
}
while (q.isNotEmpty()) {
val u = q.removeFirst()
for (v in g[u]) {
if (ans[v] == -1) {
ans[v] = ans[u] + 1 q.add(v)
}
}
}
return ans
}
}
classSolution:
defdistanceToCycle(self, n: int, edges: list[list[int]]) -> list[int]:
g = [[] for _ in range(n)]
for a, b in edges:
g[a].append(b)
g[b].append(a)
parent = [-1] * n
start = end =-1defdfs(u, p):
nonlocal start, end
parent[u] = p
for v in g[u]:
if v == p:
continueif parent[v] ==-1:
if dfs(v, u):
returnTrueelse:
start, end = v, u
returnTruereturnFalse dfs(0, -1)
in_cycle = [0] * n
x = end
while x != start:
in_cycle[x] =1 x = parent[x]
in_cycle[start] =1from collections import deque
ans = [-1] * n
q = deque()
for i in range(n):
if in_cycle[i]:
ans[i] =0 q.append(i)
while q:
u = q.popleft()
for v in g[u]:
if ans[v] ==-1:
ans[v] = ans[u] +1 q.append(v)
return ans