Skip to main content
Talentd

Distance to a Cycle in Undirected Graph - Solution & Explanation

HardPremiumFree on FleetCodeDepth-First SearchBreadth-First SearchUnion FindGraph12 min readAsked at: Microsoft, Oracle
Practice this problem

Problem Statement

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 <= 105
  • 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.

Approach Overview

Problem 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.

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:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS Cycle Detection + Multi-Source BFSO(n)O(n)When you want explicit cycle detection using DFS before computing distances
Topological Leaf Pruning + BFSO(n)O(n)Best general solution; efficiently isolates cycle nodes before BFS
Union-Find + BFSO(n α(n))O(n)Useful when union-find is already part of the solution or for incremental edge processing

Video Solution

2204. Distance to a Cycle in Undirected Graph (Leetcode Hard) • Programming Live with Larry • 571 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Distance to a Cycle in Undirected Graph easy or hard?
The problem is labeled Hard because it requires recognizing the structural property of a single-cycle graph and applying leaf pruning or cycle detection before computing distances. Once the cycle nodes are identified, the remaining BFS step is straightforward.
Distance to a Cycle in Undirected Graph Python/Java solution
Implement the topological pruning strategy: build the adjacency list, compute node degrees, remove leaves with a queue, then run a multi-source BFS from the remaining cycle nodes. The same algorithm works in Python, Java, C++, Go, and TypeScript with identical O(n) complexity.
How to solve Distance to a Cycle in Undirected Graph in O(n)?
Compute the degree of every node and push all degree-1 nodes into a queue. Repeatedly remove these leaves and decrement the degree of their neighbors until only cycle nodes remain. Initialize those cycle nodes with distance 0 and run a multi-source BFS to assign distances to all other nodes. Each node and edge is processed once, giving O(n) complexity.
What is the best approach for Distance to a Cycle in Undirected Graph?
The most effective approach removes leaf nodes iteratively using a topological pruning technique. Nodes with degree 1 are pushed into a queue and removed until only cycle nodes remain. After identifying the cycle, a multi-source BFS computes the minimum distance from each node to the cycle. This runs in O(n) time and O(n) space.
Is Distance to a Cycle in Undirected Graph asked at Google/Amazon/Meta?
Graph problems involving cycle detection, BFS distance propagation, and topological pruning appear frequently in interviews at companies like Google, Amazon, and Meta. Variants include finding cycle nodes, shortest distance to special nodes, or trimming leaves in graphs and trees.
What data structure is used in Distance to a Cycle in Undirected Graph?
The solution primarily uses adjacency lists to represent the graph, a queue for BFS or leaf pruning, and an array to track node degrees. Some variations also use recursion stacks for DFS or a union-find structure to detect cycle edges.
What is the time complexity of Distance to a Cycle in Undirected Graph?
The optimal solution runs in O(n) time where n is the number of nodes. Leaf pruning processes each node and edge once, and the subsequent multi-source BFS also visits each node at most once. Space complexity is O(n) for adjacency lists, degree tracking, and the BFS queue.

Ready to solve this problem?

Practice Distance to a Cycle in Undirected Graph with our built-in code editor and test cases.

Practice on FleetCode
Previous

Paths in Maze That Lead to Same Room