Cycle Detection

Cycle Detection (Undirected)

A cycle is a path that starts and ends at the same node. Detecting cycles is fundamental to many graph algorithms (e.g., checking if a graph is a tree).

Tree (no cycle):   Cycle:
    0                0 — 1
    |                |   |
    1                2 — 3
    |
    2

DFS with Parent Tracking

In an undirected graph, during DFS, a cycle exists if we encounter an already-visited neighbor that isn't our immediate parent.

def has_cycle(graph):
    seen = set()

    def dfs(node, parent):
        seen.add(node)
        for nb in graph[node]:
            if nb not in seen:
                if dfs(nb, node):
                    return True
            elif nb != parent:      # visited neighbor ≠ parent → cycle!
                return True
        return False

    for node in graph:
        if node not in seen:
            if dfs(node, -1):
                return True
    return False

Why ignore the parent?

In an undirected graph, every edge appears in both directions. When we visit node 1 from node 0, node 0 is in 1's neighbors. That's not a cycle — it's just the edge we came from.

Your Task

Implement has_cycle(graph) that returns True if the undirected graph contains a cycle, False otherwise. The graph is passed as an adjacency list.