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 array answer of size n, where answer[i] is the minimum distance between the ith node and any node in the cycle.
Example 1:
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 1 is 1. The distance from 1 to 1 is 0. The distance from 2 to 2 is 0. The distance from 3 to 3 is 0. The distance from 4 to 4 is 0. The distance from 5 to 2 is 1. The distance from 6 to 2 is 2.
Example 2:
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 0 is 0. The distance from 1 to 1 is 0. The distance from 2 to 2 is 0. The distance from 3 to 1 is 1. The distance from 4 to 1 is 2. The distance from 5 to 1 is 2. The distance from 6 to 2 is 1. The distance from 7 to 2 is 2. The distance from 8 to 2 is 2.
Constraints:
3 <= n <= 105edges.length == nedges[i].length == 20 <= node1i, node2i <= n - 1node1i != node2iProblem Overview: You are given an undirected graph with n nodes that contains exactly one cycle. For every node, compute the minimum number of edges required to reach any node that lies on that cycle.
Approach 1: DFS Cycle Detection + Multi-Source BFS (Time: O(n), Space: O(n))
First identify which nodes belong to the cycle using Depth-First Search. During DFS, track parent nodes and mark nodes that form the back-edge cycle. Once all cycle nodes are known, push them into a queue as starting points. Run a multi-source Breadth-First Search outward to compute the minimum distance for every non-cycle node. Each layer of BFS increases the distance by one, ensuring the first visit gives the shortest distance to the cycle.
Approach 2: Topological Pruning (Leaf Removal) + BFS (Time: O(n), Space: O(n))
This approach uses a technique similar to topological sorting on an undirected graph. Compute the degree of every node and push all leaf nodes (degree = 1) into a queue. Repeatedly remove these leaves and decrease the degree of their neighbors. Nodes that survive this pruning process must belong to the cycle because they never become leaves. After identifying cycle nodes, initialize their distance as 0 and run a multi-source BFS to propagate distances to all other nodes.
Approach 3: Union-Find Cycle Detection + BFS (Time: O(n α(n)) + O(n), Space: O(n))
Using Union Find, process edges and detect the edge that closes the cycle. With additional bookkeeping, determine which nodes are part of that cycle component. After marking cycle nodes, perform a multi-source BFS starting from them to compute distances for the rest of the graph. While union-find efficiently detects the cycle edge, extra work is required to reconstruct all cycle nodes, which makes this approach less direct.
Recommended for interviews: The topological pruning approach is usually the cleanest. It removes all tree-like branches first, leaving only cycle nodes, then computes distances with a single BFS. Demonstrating DFS-based cycle detection shows strong graph fundamentals, but the leaf-removal technique highlights deeper insight into graph structure and is often the expected optimal solution.
We can first convert the edges in edges into an adjacency list g, where g[i] represents all adjacent nodes of node i, represented as a set.
Next, we delete nodes layer by layer from the outside to the inside until only a cycle remains. The specific method is as follows:
We first find all nodes with a degree of 1 and remove these nodes from the graph. If after deletion, the degree of its adjacent node becomes 1, then we add it to the queue q. During this process, we record all deleted nodes in order as seq; and we use an array f to record the adjacent node of each node that is closer to the cycle, i.e., f[i] represents the adjacent node of node i that is closer to the cycle.
Finally, we initialize an answer array ans of length n, where ans[i] represents the minimum distance from node i to any node in the cycle, initially ans[i] = 0. Then, we start traversing from the end of seq. For each node i, we can get the value of ans[i] from its adjacent node f[i], i.e., ans[i] = ans[f[i]] + 1.
After the traversal, return the answer array ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Cycle Detection + Multi-Source BFS | O(n) | O(n) | When you want explicit cycle detection using DFS before computing distances |
| Topological Leaf Pruning + BFS | O(n) | O(n) | Best general solution; efficiently isolates cycle nodes before BFS |
| Union-Find + BFS | O(n α(n)) | O(n) | Useful when union-find is already part of the solution or for incremental edge processing |
2204. Distance to a Cycle in Undirected Graph (Leetcode Hard) • Programming Live with Larry • 558 views views
Watch 3 more video solutions →Practice Distance to a Cycle in Undirected Graph with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor