Cycle Detection (Union-Find)

In an undirected graph, a cycle exists if adding an edge (u, v) connects two nodes that are already in the same connected component. Union-Find is ideal: before adding (u, v), call find(u) and find(v); if they are equal, the edge would form a cycle.

Idea

  • Start with each node as its own component.
  • For each edge (u, v) in order:
    • If find(u) == find(v), then u and v are already connected → adding (u, v) creates a cycle.
    • Otherwise, union(u, v).

Template

Java
public boolean hasCycle(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    for (int[] e : edges) {
        int u = e[0], v = e[1];
        if (uf.find(u) == uf.find(v)) return true;
        uf.union(u, v);
    }
    return false;
}

Directed Graphs

Cycle detection in a directed graph is different: use DFS with a “gray” (in stack) set to detect back edges, or topological sort. Union-Find is for undirected graphs.

Summary

For undirected graphs, Union-Find detects a cycle when an edge is added between two nodes already in the same component. Process edges one by one; if find(u) == find(v) before union, the graph has a cycle.