Union-Find Applications

"Connect components dynamically. Detect cycles, count components, earliest connection."

Union-Find (Disjoint Set Union) efficiently answers: are two elements in the same component? It supports union (merge components) and find (get component representative) in near-O(1) amortized with path compression and union by rank. Applications: count connected components, detect cycles in undirected graphs, Kruskal's MST, earliest time when all connected, account merging.

13 min readgraph problems →

Problems you can solve with this pattern

4 problems · click any to start solving

All graph →

1Number of ProvincesMediumSolve

2Accounts MergeMediumSolve

3Earliest Moment When Everyone Become FriendsMediumSolve

4Satisfiability of Equality EquationsMediumSolve

Union-Find with path compression and rank

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = new Array(n).fill(0);
        this.count = n; // number of components
    }

    find(x) {
        if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]); // path compression
        return this.parent[x];
    }

    union(x, y) {
        const px = this.find(x), py = this.find(y);
        if (px === py) return false; // already connected
        // Union by rank
        if (this.rank[px] < this.rank[py]) this.parent[px] = py;
        else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
        else { this.parent[py] = px; this.rank[px]++; }
        this.count--;
        return true;
    }

    connected(x, y) { return this.find(x) === this.find(y); }
}

Union-Find with path compression and union by rank: find(x) = parent[x] == x ? x : parent[x] = find(parent[x]). Union(x, y): link smaller rank to larger. Track component count: decrement on each successful union. Cycle detection: union returns false if both already in same component. Weighted union-find: store weight (ratio, difference) at each edge for path queries.

Union-Find with path compression and rank

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = new Array(n).fill(0);
        this.count = n; // number of components
    }

    find(x) {
        if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]); // path compression
        return this.parent[x];
    }

    union(x, y) {
        const px = this.find(x), py = this.find(y);
        if (px === py) return false; // already connected
        // Union by rank
        if (this.rank[px] < this.rank[py]) this.parent[px] = py;
        else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
        else { this.parent[py] = px; this.rank[px]++; }
        this.count--;
        return true;
    }

    connected(x, y) { return this.find(x) === this.find(y); }
}

Medium

Medium

Earliest Moment When Everyone Become Friends

Medium

Solve

Satisfiability of Equality Equations

Medium

Solve

Union-Find amortized complexity: With both path compression and union by rank, each operation is O(α(n)) where α is the inverse Ackermann function — effectively O(1) for any practical n.

When to use Union-Find vs BFS/DFS:
- Dynamic connectivity (edges added over time): Union-Find
- Static graph, one-time query: BFS/DFS fine
- Need path between nodes: BFS/DFS
- Just need same-component check: Union-Find

Rollback Union-Find: Without path compression, use union by rank only — then union/undo is O(log n). Used in offline algorithms.

← Array Rotation & Circular Problems String Parsing & Integer Conversion →