Disjoint Set (Union-Find) Template

Disjoint Set Union (DSU) tracks a partition of N elements into disjoint groups, supporting near-constant-time `find` (which group?) and `union` (merge two groups). It is the building block for Kruskal's MST, connected components on dynamic graphs, and the redundant-connection problem. This snippet covers the parent-array skeleton, the path-compression optimisation that flattens trees on every find, and the union-by-rank merge that keeps trees shallow.

JavaScript

Hard

data-structures

union-find

code-template

algorithms

710 views

Parent array skeleton

Ask AI

class DSU {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
    }
    find(x) {
        while (this.parent[x] !== x) x = this.parent[x];
        return x;
    }
    union(a, b) {
        const ra = this.find(a);
        const rb = this.find(b);
        if (ra === rb) return false;
        this.parent[ra] = rb;
        return true;
    }
    connected(a, b) { return this.find(a) === this.find(b); }
}

const dsu = new DSU(5);
dsu.union(0, 1);
dsu.union(1, 2);
console.log(dsu.connected(0, 2)); // true
console.log(dsu.connected(0, 4)); // false

Each element starts as its own root (parent[i] = i). find walks parent pointers until it reaches a self-loop, which is the group's representative. union finds both representatives and re-parents one under the other. Without optimisations, the trees can degenerate into linked lists and find becomes O(n), so this naive version is O(n) per operation in the worst case. The two next accordions add the standard optimisations to reach near-constant time.

2 more snippets in this entry are available for premium members.

Upgrade to Premium

Back to Code Snippets