An efficient Disjoint Set implementation (using compressed trees and dense storage).

DisjointSet.ts

/**
 * (If a number is used, it must be > -1!)
 */
type DSNode = number | string;

class DisjointSet {
    protected readonly parents: Map<DSNode, DSNode | number> = new Map();
    protected count = 0;

    protected findRoot(node: DSNode): DSNode {
        const parent = this.parents.get(node) ?? -1;
        // If parent's value is < 0, it's actually the rank value
        // of the node (which is the root of its tree).
        if (parent < 0) return node;

        const root = this.findRoot(parent); // <--- Tree compression ❤️
        this.parents.set(node, root);

        return root;
    }

    public add(node: DSNode): void {
        if (this.parents.get(node) !== undefined) return;

        this.parents.set(node, -1);
        this.count++;
    }

    // Values must be >= 0!
    public union(a: DSNode, b: DSNode): void {
        // We need to add the nodes if we haven't already...
        this.add(a);
        this.add(b);

        const aRoot = this.findRoot(a);
        const bRoot = this.findRoot(b);

        // If roots are equal, they're already in the same tree and 
        // there's nothing we need to do.
        if (aRoot === bRoot) return;

        const aRank = this.parents.get(aRoot) as number;
        const bRank = this.parents.get(bRoot) as number;

        // (Rank ordering is reversed, as we use negative numbers to 
        // differentiate from node names.)
        if (aRank < bRank) {
            // Attach A to B and update its rank, to include B's 
            // previous rank.
            this.parents.set(aRoot, aRank + bRank);
            this.parents.set(bRoot, aRoot);
            this.count--;
        } else {
            this.parents.set(bRoot, aRank + bRank);
            this.parents.set(aRoot, bRoot);
            this.count--;
        }
    }

    public getCount(): number {
        return this.count;
    }
}