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.

Description Hints 3 Solution Video 17:13

2204. Distance to a Cycle in Undirected Graph

Hard73.4% acceptance2 companiesPremium elsewhere, free here

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] = [node1_i, node2_i] denotes that there is a bidirectional edge connecting node1_i and node2_i 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 i^th 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 <= 10⁵
edges.length == n
edges[i].length == 2
0 <= node1_i, node2_i <= n - 1
node1_i != node2_i
The graph is connected.
The graph has exactly one cycle.
There is at most one edge between any pair of vertices.

Asked at 2 companies

Oracle Microsoft

Topics

Hints open one at a time

Hint 1

This problem can be broken down into two parts: finding the cycle, and finding the distance between each node and the cycle.

Hint 2

How can we find the cycle? We can use DFS and keep track of the nodes we’ve seen, and the order that we see them in. Once we see a node we’ve already visited, we know that the cycle contains the node that was seen twice and all the nodes that we visited in between.

Hint 3

Now that we know which nodes are part of the cycle, how can we find the distances? We can run a multi-source BFS starting from the nodes in the cycle and expanding outward.

17:13

Still stuck?Read the written solution, or watch a walkthrough.

Open solution