Distance to a Cycle in Undirected Graph
Asked at Salesforce
Problem
Given an undirected connected graph with exactly one cycle, find the distance from every node to the nearest node on that cycle.
Asked At
| 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.
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
from 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.