Solution Explanation: Distance to a Cycle in Undirected Graph

This problem asks to find the minimum distance from each node to any node in the cycle of a connected undirected graph with exactly one cycle. The optimal solution uses a topological sorting approach combined with breadth-first search (BFS) concepts. Let's break down the solution step-by-step:

1. Graph Representation:

The input edges is first converted into an adjacency list representation. This allows efficient access to neighbors of each node. For example, g[i] will store a set (or list) containing all nodes directly connected to node i.

2. Topological Sorting (Outer Nodes Removal):

The core idea is to iteratively remove nodes that are on the periphery of the graph (nodes with degree 1, meaning they only have one neighbor). This is effectively a topological sort of the acyclic part of the graph.

• Queue Initialization: A queue q is initialized with all nodes of degree 1. These are the starting points for the removal process.

• Iterative Removal: The algorithm iterates while the queue q is not empty. In each iteration:

  • A node i is dequeued from q.
  • This node i is added to the seq (sequence) list, indicating its distance from the cycle.
  • The neighbor j of i (the only neighbor since degree is 1) has its edge to i removed (g[j].remove(i)). f[i] is set to j, indicating j is the closest node to the cycle from i.
  • If removing the edge to i reduces the degree of j to 1, j is added to q, as it's now a peripheral node.

• Resulting seq: The seq list, after the process, contains nodes ordered from furthest to closest to the cycle.

3. Distance Calculation (Inner Nodes):

Once the peripheral nodes are removed, we're left with the cycle itself. The distance calculation uses the seq list (in reverse) and the f array.

• Initialization: An array ans of size n is initialized with zeros, representing the distances from each node to the cycle.

• Iterative Calculation: seq is traversed in reverse order (from the closest to the furthest from the cycle). For each node i in seq:

  • ans[i] is set to ans[f[i]] + 1. This effectively calculates the distance to the cycle by adding 1 to the distance of its closest neighbor (f[i]).

4. Return ans:

The array ans, containing the minimum distances from each node to any node in the cycle, is returned.

Time Complexity: O(n) - Each node is visited and processed at most once in both the node removal and distance calculation phases.

Space Complexity: O(n) - The adjacency list g, the queue q, the sequence seq, and the distance array ans all have a maximum size proportional to the number of nodes n.

Example in Python (Illustrative):

Let's take a simplified example: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0]] (a cycle).

1. The adjacency list g would be created.
2. The queue q would be initially empty because no node has degree 1. (This case doesn't follow the problem statement perfectly because there is no node outside the cycle.) In a graph with nodes outside the cycle, those outer nodes would start in q.
3. The iterative removal and distance calculation phases would be skipped in this cycle-only scenario, and ans would be [0, 0, 0, 0, 0] since every node is in the cycle.

A graph with nodes outside the cycle would demonstrate the topological sort and distance calculation more clearly. The provided Python, Java, C++, Go, and TypeScript code implements this algorithm effectively.