When a search loops back
A cycle in an undirected graph is a path that returns to its starting vertex without reusing an edge. Detecting cycles tells you whether a graph is a tree or a forest, since those are exactly the acyclic connected structures.
The parent aware DFS
During a depth first search, you remember the parent, the vertex you came from. When exploring a neighbour:
- If the neighbour is unvisited, recurse into it and pass the current vertex as its parent.
- If the neighbour is already visited and is not the parent, you have found a cycle.
The parent check matters because the edge back to your parent is the same edge you just traversed, not a genuine second route. Without it, every single edge would falsely look like a cycle.
Union find alternative
You can also process edges one at a time with union find. For each edge, if its two endpoints are already in the same set, adding the edge would close a loop, so a cycle exists. Otherwise you union the two sets.
A connected undirected graph with more edges than vertices minus one must contain a cycle.
Key idea
In an undirected graph a cycle exists when a DFS reaches an already visited vertex that is not its parent, or when union find sees both endpoints of an edge already joined.