Cycle Detection in Undirected Graphs
from collections import deque
# DFS approach: track parent to distinguish back edge from tree edge
def has_cycle_undirected(n: int, edges: list) -> bool:
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
def dfs(node, parent) -> bool:
visited[node] = True
for neighbor in graph[node]:
if not visited[neighbor]:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True # back edge to non-parent = cycle
return False
for i in range(n):
if not visited[i]:
if dfs(i, -1):
return True
return False
# Union-Find approach: O(E * alpha(V)) - preferred for dynamic edge addition
def has_cycle_uf(n: int, edges: list) -> bool:
parent = list(range(n))
rank = [0] * n
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y) -> bool:
px, py = find(x), find(y)
if px == py:
return False # cycle detected
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return True
return FalseCycle Detection in Directed Graphs
# DFS with color marking: WHITE=0 (unvisited), GRAY=1 (in stack), BLACK=2 (done)
def has_cycle_directed(n: int, edges: list) -> bool:
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
color = [0] * n # 0=white, 1=gray, 2=black
def dfs(node) -> bool:
color[node] = 1 # mark as in-progress
for neighbor in graph[node]:
if color[neighbor] == 1:
return True # back edge = cycle
if color[neighbor] == 0 and dfs(neighbor):
return True
color[node] = 2 # mark as done
return False
for i in range(n):
if color[i] == 0:
if dfs(i):
return True
return False
# Kahn's BFS (topological sort): if not all nodes are processed -> cycle exists
def has_cycle_kahn(n: int, edges: list) -> bool:
in_degree = [0] * n
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
processed = 0
while queue:
node = queue.popleft()
processed += 1
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return processed != n # if not all processed -> cycleFloyd’s Cycle Detection (Linked List)
# Detect cycle in linked list (LC 141) - O(1) space
def has_cycle_ll(head) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
# Find entry point of cycle (LC 142)
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # no cycle
# Move one pointer to head, advance both at speed 1
# They meet at the cycle entry point
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
# Mathematical proof: if cycle length is C and pre-cycle length is F,
# meeting point is F steps from entry. Moving head pointer F steps reaches entry.
# Find duplicate in array [1..n] treated as linked list (LC 287)
def find_duplicate(nums: list[int]) -> int:
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slowWhich Algorithm to Use
Undirected graph cycle detection: DFS with parent tracking (simple, O(V+E)) or Union-Find (preferred when edges are added dynamically, O(E * alpha(V))). Directed graph cycle detection: DFS with 3-color marking (WHITE/GRAY/BLACK) detects back edges, or Kahn’s BFS topological sort (processed_count != n means cycle exists). Kahn’s is often more intuitive in interviews. Linked list cycle detection: Floyd’s slow/fast pointer for O(1) space. Use the same technique for LC 287 (find duplicate) by treating the array as a linked list. Common interview questions: LC 141/142 (linked list cycle), LC 207/210 (course schedule – directed graph), LC 684/685 (redundant connection – undirected/directed).
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the difference between cycle detection in directed vs undirected graphs?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”In undirected graphs, a cycle exists when DFS encounters a visited node that is not the direct parent of the current node. The parent check avoids treating the edge we came from as a back edge. In directed graphs, a cycle exists when DFS encounters a GRAY node (currently in the recursion stack) – this indicates a back edge. A visited BLACK node is not a cycle in a directed graph because that node was fully processed via a different path. Use 3-color marking (WHITE/GRAY/BLACK) for directed graphs, parent-tracking for undirected.”}},{“@type”:”Question”,”name”:”When should you use Union-Find vs DFS for cycle detection?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use Union-Find when edges are added dynamically (online algorithm) or when you only need to detect the cycle without finding its path. Union-Find runs in O(E * alpha(V)) – nearly O(E). Use DFS when you need to find the actual cycle path, detect specific types of cycles (back edges), or work with directed graphs (Union-Find only works naturally for undirected graphs). For LC 684 (Redundant Connection), Union-Find is ideal. For LC 207 (Course Schedule, directed), use DFS 3-color or Kahn's BFS.”}},{“@type”:”Question”,”name”:”How does Floyd's cycle detection algorithm work for linked lists?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Floyd's algorithm uses two pointers: slow (moves 1 step) and fast (moves 2 steps). If a cycle exists, fast will lap slow within the cycle, and they will meet. If no cycle, fast reaches null. To find the cycle entry point: after meeting, reset slow to head and advance both pointers one step at a time. They meet at the cycle entry point. Mathematical proof: if the pre-cycle length is F and meeting point is M steps into the cycle, then F = C – M (mod C) where C is cycle length. So moving F steps from head reaches the same position as moving F steps from the meeting point within the cycle.”}},{“@type”:”Question”,”name”:”How do you detect a cycle in a directed graph using Kahn's algorithm?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Compute in-degree for all nodes. Add all nodes with in-degree 0 to a queue. BFS: process each node, decrement in-degree of its neighbors, add newly zero-in-degree neighbors to the queue. Count processed nodes. If the count equals total nodes: no cycle (graph is a DAG). If count is less than total nodes: a cycle exists. The unprocessed nodes are those in cycles – their in-degree never reaches 0. This approach is preferred in interviews for being intuitive and easy to modify to return the topological order.”}},{“@type”:”Question”,”name”:”How do you find a duplicate number in an array using Floyd's algorithm?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”LC 287: given array nums of n+1 integers in range [1,n], find the duplicate. Treat the array as a linked list: index i points to nums[i]. Since there is a duplicate, the graph has a cycle. Apply Floyd's algorithm: slow = nums[slow], fast = nums[nums[fast]]. After they meet, reset slow = nums[0] and advance both by 1. Where they meet is the duplicate value. This runs in O(n) time and O(1) space without modifying the input array – better than sorting (O(n log n)) or a hash set (O(n) space).”}}]}
Meta coding interviews frequently test cycle detection in graphs. See common patterns at Meta interview: cycle detection and graph problems.
LinkedIn interviews include linked list cycle detection and graph problems. See patterns for LinkedIn interview: graph and linked list problems.
Atlassian coding rounds include graph cycle detection. Review patterns for Atlassian interview: graph cycle detection problems.