How do I detect cycles in a graph?
Use Depth-First Search (DFS) or union-find to detect cycles in a graph.
Cycle detection is a common task in graph-related problems. One way to detect cycles is to use Depth-First Search (DFS), marking nodes as you traverse the graph. If you revisit a node that is already marked as 'in progress' (i.e., you haven't finished exploring all its descendants), you've found a cycle. For undirected graphs, you can also use the union-find (disjoint set) data structure to detect cycles efficiently by tracking which nodes are connected. These techniques are particularly useful for problems involving connectivity or graph traversal where cycles can indicate invalid states or infinite loops.