Union-Find

// 1) Core data structure
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) {
        // Path compression — every node on the path points directly at the root after this call
        while (this.parent[x] !== x) {
            this.parent[x] = this.parent[this.parent[x]];
            x = this.parent[x];
        }
        return x;
    }

    union(x, y) {
        const rx = this.find(x), ry = this.find(y);
        if (rx === ry) return false;                       // already in same set
        // Union by rank — attach the shallower tree under the deeper
        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]++; }
        this.count--;
        return true;
    }

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

// 2) Demo
const uf = new UnionFind(8);
uf.union(0, 1); uf.union(1, 2); uf.union(3, 4); uf.union(5, 6);
uf.connected(0, 2);    // true
uf.connected(0, 4);    // false
uf.count;              // 5 components: {0,1,2} {3,4} {5,6} {7} … wait, count is 4 — 8 - 4 unions = 4

// 3) Counting connected components from an edge list
function componentCount(n, edges) {
    const uf = new UnionFind(n);
    for (const [a, b] of edges) uf.union(a, b);
    return uf.count;
}

componentCount(8, [[0,1],[1,2],[3,4],[5,6]]);    // 4 (one singleton: node 7)

// 4) Cycle detection in an undirected graph
function hasCycle(n, edges) {
    const uf = new UnionFind(n);
    for (const [a, b] of edges) {
        if (!uf.union(a, b)) return true;            // already connected -> adding this edge closes a cycle
    }
    return false;
}

// 5) Kruskal's algorithm — minimum spanning tree on a weighted graph
function mstWeight(n, edges) {
    // edges: [a, b, weight]
    const uf = new UnionFind(n);
    let weight = 0, used = 0;
    for (const [a, b, w] of edges.slice().sort((x, y) => x[2] - y[2])) {
        if (uf.union(a, b)) {
            weight += w;
            if (++used === n - 1) break;
        }
    }
    return used === n - 1 ? weight : Infinity;
}

// 6) Friend circles / number-of-islands (graph variants)
function friendCircles(M) {
    const n = M.length;
    const uf = new UnionFind(n);
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (M[i][j]) uf.union(i, j);
        }
    }
    return uf.count;
}

// 7) Number of islands by union over grid neighbours
function numIslands(grid) {
    const R = grid.length, C = grid[0].length;
    const uf = new UnionFind(R * C);
    let zeros = 0;
    const id  = (r, c) => r * C + c;
    for (let r = 0; r < R; r++) {
        for (let c = 0; c < C; c++) {
            if (grid[r][c] === '0') { zeros++; continue; }
            if (r > 0 && grid[r - 1][c] === '1') uf.union(id(r, c), id(r - 1, c));
            if (c > 0 && grid[r][c - 1] === '1') uf.union(id(r, c), id(r, c - 1));
        }
    }
    return uf.count - zeros;        // subtract the singleton water cells
}

// 8) Dynamic connectivity (offline)
// Process a stream of operations:
//   union(a, b)
//   query(a, b) -> are they connected?
// Easy: just run union and find as they arrive.
// Watch out for OFFLINE deletes (edges removed) — that's a different beast (link-cut trees or LCT).

// 9) Accounts merge — group accounts by shared email
function accountsMerge(accounts) {
    const emailToIdx = new Map();
    const uf = new UnionFind(accounts.length);
    accounts.forEach(([name, ...emails], i) => {
        for (const e of emails) {
            if (emailToIdx.has(e)) uf.union(i, emailToIdx.get(e));
            else                    emailToIdx.set(e, i);
        }
    });
    const byRoot = new Map();
    emailToIdx.forEach((idx, email) => {
        const r = uf.find(idx);
        if (!byRoot.has(r)) byRoot.set(r, new Set());
        byRoot.get(r).add(email);
    });
    return [...byRoot].map(([root, set]) => [accounts[root][0], ...[...set].sort()]);
}

// 10) Weighted union-find — track relative offsets between nodes
class WeightedUF {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.weight = new Array(n).fill(0);      // weight[x] = offset from x to parent
    }
    find(x) {
        if (this.parent[x] === x) return x;
        const root = this.find(this.parent[x]);
        this.weight[x] += this.weight[this.parent[x]];
        this.parent[x] = root;
        return root;
    }
    union(x, y, diff) {                          // y - x = diff
        const rx = this.find(x), ry = this.find(y);
        if (rx === ry) return this.weight[y] - this.weight[x] === diff;
        this.parent[rx] = ry;
        this.weight[rx] = diff + this.weight[y] - this.weight[x];
        return true;
    }
}

// 11) Complexity
//   Without compression / rank: O(n) per op worst case
//   With path compression + union by rank: O(α(n)) per op amortised — α grows < 5 for any conceivable n

// 12) When NOT to use union-find
//   • You need to SPLIT groups dynamically — union-find doesn't support undo or split cleanly
//   • You need to enumerate members in a group — store a separate list keyed by root
//   • Online deletions of edges — too expensive without specialised data structures
//   • You need shortest paths — use BFS / Dijkstra

// 13) Common bugs
//   • Forgetting to do path compression in find() → O(n) per op on adversarial inputs
//   • Updating parent[x] without re-running find on the children → stale pointers in iteration
//   • Using object literals for parent map with non-integer keys → use Map for clarity
//   • Counting components by uniqueing parent[i] WITHOUT calling find — gives the wrong answer
//   • Forgetting to decrement count on a successful union

class DSU {
    constructor(n) { this.p = [...Array(n).keys()]; this.r = Array(n).fill(0); }
    find(x) { return this.p[x] === x ? x : (this.p[x] = this.find(this.p[x])); }
    union(a, b) {
        a = this.find(a); b = this.find(b);
        if (a === b) return false;
        if (this.r[a] < this.r[b]) [a, b] = [b, a];
        this.p[b] = a;
        if (this.r[a] === this.r[b]) this.r[a]++;
        return true;
    }
}