Pattern Recognition Drill
Medium Graphs
The Problem
Detect if an undirected graph contains a cycle.
What approach would you use?
Think about it before scrolling down.
DFS tracking parent. If a neighbor is visited and not the parent → cycle found. O(V+E).
BFS with parent tracking also works. Same logic: visited non-parent neighbor = cycle.
Common Trap
In undirected graphs, every edge appears twice. You must track the parent to avoid false positives.