2204. Distance to a Cycle in Undirected Graph
Asked at Salesforce
Difficulty
Hard
Time
O(n + m)
Space
O(n + m)
Pattern
Depth-First Search
Companies
1
Problem
You get a connected undirected graph with n nodes (numbered 0 to n-1) and exactly one cycle. The edges are given as a list of pairs; each pair means the two nodes are joined in both directions.
The distance between two nodes is the smallest number of edges you must walk to get from one to the other. For every node, find the distance to the closest node that lies on the cycle. Nodes on the cycle itself have distance 0.
Return an array answer of length n, where answer[i] is the distance from node i to the nearest cycle node.
Distance to the single cycle
Constraints
- ●
3 <= n <= 10^5 - ●
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.
Examples
n = 7, edges = [[1,2],[2,4],[4,3],[3,1],[0,1],[5,2],[6,5]][1,0,0,0,0,1,2]n = 9, edges = [[0,1],[1,2],[0,2],[2,6],[6,7],[6,8],[0,3],[3,4],[3,5]][0,0,0,1,2,2,1,2,2]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Salesforce | Hard | View all Salesforce questions → |
How to Think About It
Brute force: for each node, run BFS to find the shortest path to any cycle node. Time is O(n * (n + m)) which is too slow.
First find the cycle using DFS. Track parent pointers and detect a back edge. The cycle nodes are on the path between the back-edge endpoints.
Once cycle nodes are identified, mark them. Then run a multi-source BFS from all cycle nodes simultaneously. The BFS distance to each node is the answer.
Multi-source BFS initializes the queue with all cycle nodes at distance 0. BFS naturally finds the shortest distance to the nearest cycle node.
To extract cycle nodes from a DFS, when a back edge (u, v) is found (where v is an ancestor of u), walk from u back to v using parent pointers.
Example: Graph 1-2-3-4-5-2 creates cycle 2-3-4-5. Node 1 is at distance 1 from cycle node 2. Node 6 attached to 3 is at distance 1. BFS from {2,3,4,5} gives distances [1,0,0,0,0,1].
Optimal Approach
Step 1: Build the adjacency list from the edge list.
Step 2: Run DFS to find the cycle. Maintain a parent array and a visited array. When you encounter a visited node that is not the parent, a back edge exists. Record (current, neighbor) as the cycle endpoints.
Step 3: Extract all cycle nodes by tracing parent pointers from both endpoints of the back edge until they meet.
Step 4: Run multi-source BFS starting from all cycle nodes with distance 0. For each unvisited neighbor, set dist[neighbor] = dist[current] + 1 and enqueue it.
Step 5: Return the distance array.
Step 6: Example walkthrough: edges = [(1,2),(2,3),(3,4),(4,5),(5,2)]. DFS from 1: 1->2->3->4->5. At 5, neighbor 2 is visited and not parent (parent of 5 is 4), so back edge (5,2) found. Trace from 5: parent[5]=4, parent[4]=3, parent[3]=2. Trace from 2: stop. Cycle = {2,3,4,5}. BFS from {2,3,4,5}: node 1 (neighbor of 2) gets dist 1. All cycle nodes get dist 0. Result: [1,0,0,0,0].
Time: O(n + m) for DFS and BFS. Space: O(n + m) for adjacency list and auxiliary arrays.
Find the cycle, then BFS outward
What Trips People Up in Real Interviews
Trying to find the cycle by looking for nodes with degree 1 and peeling layers (topological-like). This works for trees but not for graphs with exactly one cycle.
Running BFS from each node individually instead of multi-source BFS from all cycle nodes at once, leading to O(n^2) time.
Not correctly extracting all cycle nodes when a back edge is found. You must trace back through parent pointers from both endpoints.
Confusing directed graph cycle detection with undirected. In undirected graphs, the edge to the parent is not a back edge - you need to track visited status carefully.
Forgetting that the graph is connected but may have leaf nodes. The BFS approach naturally handles this since non-cycle nodes will be reached from their nearest cycle node.
Solution Code
O(n + m) timefrom collections import deque, defaultdict
def distanceToCycle(n: int, edges: list[list[int]]) -> list[int]:
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
parent = [-1] * n
visited = [False] * n
back_edge = None
def dfs(u, p):
nonlocal back_edge
visited[u] = True
parent[u] = p
for v in adj[u]:
if v == p:
continue
if visited[v]:
back_edge = (u, v)
else:
dfs(v, u)
dfs(0, -1)
cycle_nodes = set()
u, v = back_edge
path_from_u = []
while u != -1:
path_from_u.append(u)
u = parent[u]
path_from_v = []
while v != -1:
path_from_v.append(v)
v = parent[v]
i = len(path_from_u) - 1
j = len(path_from_v) - 1
while i >= 0 and j >= 0 and path_from_u[i] == path_from_v[j]:
cycle_nodes.add(path_from_u[i])
i -= 1
j -= 1
cycle_nodes.add(back_edge[0])
cycle_nodes.add(back_edge[1])
dist = [-1] * n
q = deque()
for node in cycle_nodes:
dist[node] = 0
q.append(node)
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
q.append(v)
return distFrequently Asked Questions
What is the Distance to a Cycle in Undirected Graph problem?
Given an undirected connected graph with exactly one cycle, find the distance from every node to the nearest node on that cycle.
How do you solve Distance to a Cycle in Undirected Graph?
The optimal approach runs in O(n + m) time and O(n + m) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Distance to a Cycle in Undirected Graph?
Distance to a Cycle in Undirected Graph is asked at Salesforce. It is a hard difficulty problem.
What are common mistakes on Distance to a Cycle in Undirected Graph?
- Trying to find the cycle by looking for nodes with degree 1 and peeling layers (topological-like). This works for trees but not for graphs with exactly one cycle.
- Running BFS from each node individually instead of multi-source BFS from all cycle nodes at once, leading to `O(n^2)` time.
- Not correctly extracting all cycle nodes when a back edge is found. You must trace back through parent pointers from both endpoints.
- Confusing directed graph cycle detection with undirected. In undirected graphs, the edge to the parent is not a back edge - you need to track visited status carefully.
- Forgetting that the graph is connected but may have leaf nodes. The BFS approach naturally handles this since non-cycle nodes will be reached from their nearest cycle node.