Watch 4 video solutions for Distance to a Cycle in Undirected Graph, a hard level problem involving Depth-First Search, Breadth-First Search, Union Find. This walkthrough by Programming Live with Larry has 558 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |