Graph Exploration Target: 15s
Track parent to avoid counting the edge we came from. If neighbor is visited and not parent → cycle.
def hasCycleUndirected(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = [False] * n
def dfs(u, parent):
visited[u] = True
for v in graph[u]:
if not visited[v]:
if dfs(v, u): return True
elif v != parent: # visited and not parent → cycle
return True
return False
return any(not visited[i] and dfs(i, -1) for i in range(n))Type it from memory. Go.