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