Disjoint-set union: merge sets and compress paths

One element, one set — until a merge

A disjoint-set union structure (DSU), also called union–find, maintains a partition: each element belongs to exactly one nonempty set, and sets never overlap. Initially each of the n elements forms a singleton. union(a, b) joins their entire sets; it does not just link two individual members.

find(v) returns the set’s representative. same(a, b) compares two representatives. A successful union returns true and reduces the set count by one; a repeated union returns false. find and same can change parent pointers through compression even though set membership stays the same.

Parent trees and representatives

Each element stores a parent. A root points to itself; following parents always reaches that root. All elements with the same root form one set. The root is a convenient representative, not necessarily the smallest label or the first argument of the latest union. A merge may change it.

The player draws arrows from a child to its parent; a double circle marks a root. Self-links are omitted from the drawing and remain visible in the parent table. These are auxiliary DSU links, not edges of an input graph. DSU alone cannot reconstruct a route between connected graph vertices.

Attach the smaller set to the larger

Find both roots. If they match, the sets are already joined. Otherwise compare their sizes and make the smaller set’s root a child of the larger set’s root. Add the two sizes at the surviving root. Equal sizes are resolved in favor of the first argument’s root, so the example is reproducible.

Only sizes stored at roots are meaningful. A former root keeps an obsolete array value that is not read when deciding later merges; the table displays a dash there. Linking roots preserves the forest. When an element’s depth increases in union by size, its set at least doubles, bounding depth by floor(log₂ n) before compression.

Find the root, then shorten the path

This example uses full path compression in two passes. The first follows parents to the root. The second redirects every element on that original path straight to the root. A change is shown separately, in purple. Other branches stay as they were until a later search visits them.

In the default run, union A B, union C D and union A C make D → C → A. A second balanced group grows under E; union A E then makes H → G → E → A. The first find H follows three links and changes H’s and G’s parents to A. The next find H follows just one link. The set still contains all eight elements.

What stays true after each change

Parent links form a forest, every element reaches exactly one root, and the size at each root equals its set’s element count. Initially this holds for singleton sets. A merge joins two distinct roots and decreases the root count by one. Compression points to an ancestor in the same tree, so it creates neither a cycle nor a new set.

Thus equal representatives mean equal sets, and unequal representatives mean different sets. In the default run same A E is false before the final merges; same D H is true afterwards. union B H then returns false. It does not add size twice or decrease the set count again.

Connectivity, Kruskal and its limits

When adding undirected graph edges, call union for each pair of endpoints. A connectivity query becomes same. Kruskal uses this to reject an edge whose endpoints are already connected; maze generation by Kruskal uses the same idea to avoid a cycle. The DSU trees need not resemble the accepted graph edges.

Ordinary DSU supports merging, not splitting sets or deleting arbitrary graph edges. It does not find shortest paths, handle directed reachability or list all members in constant time. The groups displayed here are derived by inspecting every element. Playback backwards restores saved visualization snapshots; it does not implement rollback DSU.

Read and edit the example

The operation list is executed from top to bottom. Use find H, union A B and same D H, one per line; letters are case-insensitive. Set the element count from 1 to 8 (A through H) and enter at most 32 operations. Empty lines are ignored and an empty list is valid. Apply restarts from singleton sets; invalid input keeps the current valid run.

The table gives each element’s parent and its size if it is a root. Text groups show actual set membership, so the canvas is not the only source of state. Counters record completed commands, successful merges, parent links followed during the first find pass, and parent pointers actually changed by compression. They exclude display reads, root comparisons, merge writes and unchanged compression assignments.

Shared controls support play/pause, steps, seek, speed, fullscreen and a link restoring the input and paused step in a clean player. Video export records the forest, table, counters and current action silently. Animation speed is a teaching aid, not a benchmark.

Nearly constant amortized cost

Initialization uses O(n) time and memory. With union by size and path compression, m find/union/same commands take O(n + m α(n)) total time, where α is the inverse Ackermann function, which grows extremely slowly. This is an amortized bound over a sequence; it is not a worst-case constant-time promise for every find. A single operation takes O(log(n+1)) in the worst case. same and union perform at most two finds.

The iterative algorithm uses O(n) storage for parent and size and O(1) additional space per command. The visualization also stores immutable snapshots. If S frames are emitted, history takes O(S(n+m)) space because each frame copies arrays and the answers so far. Deriving roots for each frame costs O(n log(n+1)); the bounded editor limits these presentation costs. They are separate from DSU’s algorithmic bound.

JavaScript implementation

This standalone implementation uses the same two-pass compression, union-by-size rule and tie order as the player, without animation history. Elements are numbered 0 to n−1. Validate both arguments before a binary command so an invalid second argument does not partially compress the first path. Keep parent and size as internal state in application code.

class DSU {
    constructor(n) {
        if (!Number.isInteger(n) || n < 1)
            throw new RangeError("Expected a positive element count");
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.size = Array(n).fill(1);
        this.components = n;
    }
    check(v) {
        if (!Number.isInteger(v) || v < 0 || v >= this.parent.length)
            throw new RangeError("Invalid element");
    }
    find(v) {
        this.check(v);
        let root = v;
        while (this.parent[root] !== root) root = this.parent[root];
        // Second pass: every visited element points straight to the root.
        while (v !== root) {
            const next = this.parent[v];
            this.parent[v] = root;
            v = next;
        }
        return root;
    }
    union(a, b) {
        this.check(a); this.check(b);
        a = this.find(a); b = this.find(b);
        if (a === b) return false;
        if (this.size[a] < this.size[b]) [a, b] = [b, a];
        this.parent[b] = a;
        this.size[a] += this.size[b];
        this.components--;
        return true;
    }
    same(a, b) {
        this.check(a); this.check(b);
        return this.find(a) === this.find(b);
    }
}

const dsu = new DSU(4); // A=0, B=1, C=2, D=3
dsu.union(0, 1);
dsu.union(2, 3);
dsu.union(0, 2);        // D → C → A
dsu.find(3);           // 0; now D → A
dsu.same(1, 3);        // true
dsu.union(1, 3);       // false: already in the same set