Medium DFS + Parent Graphs
In plain English: Determine whether an undirected graph contains any loop.
In DFS, a visited neighbor that isn't your parent means you've found a back edge — proof that a cycle exists.
Prompt
Detect if an undirected graph contains a cycle.
Try to write it from scratch before scrolling down.
Solution
def has_cycle(graph, n):
visited = set()
def dfs(node, parent):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
if dfs(nb, node):
return True
elif nb != parent: # visited + not parent = back edge = cycle
return True
return False
for i in range(n):
if i not in visited:
if dfs(i, -1):
return True
return False