Union-find (disjoint set)

near O(1) per op

Give every element a parent pointer; following parents upward reaches a root that names the group. find walks up to the root, union joins two roots, and path compression plus union by rank keep both operations near O(1).

Signals

are these two in the same groupmerge/union facts arrive one at a timedynamic connectivity as edges are addedaccount/friend merging over timeadding this edge would create a cycle

Template

class UnionFind {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }
    find(x) {
        if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x, y) {
        const rx = this.find(x), ry = this.find(y);
        if (rx === ry) return false;
        if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
        else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
        else { this.parent[ry] = rx; this.rank[rx]++; }
        return true;
    }
}

Looks similar, isn't

Connected components: Union-find answers 'same group?' as edges arrive one at a time, interleaved with the merges. Component flood-fill assumes the whole graph is fixed before you start counting.

n up to 1e5..1e6 elements, m union/find queries interleaved over time -> O(m alpha(n)) total, alpha being the near-constant inverse-Ackermann function.

Learn this pattern