← All patterns

Union Find

Disjoint-set forest with path compression and union by rank. Maintain connected components dynamically as edges arrive in near-O(1) per op (inverse Ackermann).

14 problems 1 Easy 7 Medium 6 Hard

Disjoint-set forest tracks connected components dynamically as edges are added. Each node points to a 'parent'; `find` walks to the root with path compression; `union` merges roots by rank (or size). Both operations are near-O(1) amortized (inverse Ackermann).

Use when edges arrive incrementally — a DFS / BFS reachability check would need a re-run per query. With DSU, each query is essentially O(1).

When to reach for this pattern

  • Dynamic connectivity: edges arrive over time
  • Find connected components in a graph
  • Minimum spanning tree (Kruskal's)
  • Group entities by equivalence relation (accounts merge, similar strings)

Canonical template 

struct DSU {
    vector<int> p, r;
    DSU(int n) : p(n), r(n, 0) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (r[x] < r[y]) swap(x, y);
        p[y] = x;
        if (r[x] == r[y]) ++r[x];
        return true;
    }
};

C++ · adapt the names and types to your problem.

Common pitfalls

  • Forgetting path compression — degrades to O(log n) or worse per op
  • Plain union without rank/size — O(n) worst-case chain
  • Tracking component sizes / counts: keep a side array, don't recompute from parents
  • Edge-list iteration after building DSU — remember find returns roots, not labels

Related patterns

Graphs Tree DFS Hash Maps

Problems (14)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.