How do you detect a cycle in an undirected graph?

Short answer: DFS while tracking parent: visiting an already-visited neighbor that is not the parent means a cycle. Union-Find (Disjoint Set) also works for edge lists: union fails if both ends share a parent.

Complexity

Time O(V + E).

Do not reuse the directed-graph “gray node” story without adjusting for parent.