Union-Find (Disjoint Set Union)

"Find the root. Union the sets. Near-constant time with path compression."

Union-Find (DSU) answers two questions in near-O(1): "are two elements in the same group?" and "merge two groups." With path compression and union by rank, both operations are amortized O(α(n)) — effectively constant. Solves connectivity, cycle detection, and MST problems.

16 min readgraph problems →

Problems you can solve with this pattern

7 problems · click any to start solving

All graph →

1Number of IslandsMediumSolve

2Redundant ConnectionMediumSolve

3Accounts MergeMediumSolve

4Number of Connected Components in an Undirected GraphMediumSolve

Union-Find with path compression + union by rank

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank   = new Array(n).fill(0);
        this.count  = n; // number of connected components
    }

    find(x) {
        // Path compression: flatten tree — every node points directly to root
        if (this.parent[x] !== x)
            this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }

    union(x, y) {
        const px = this.find(x), py = this.find(y);
        if (px === py) return false; // already connected
        // Union by rank: attach smaller tree under larger
        if (this.rank[px] < this.rank[py]) this.parent[px] = py;
        else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
        else { this.parent[py] = px; this.rank[px]++; }
        this.count--;
        return true;
    }

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

// Simpler functional version (when rank not needed):
const parent = Array.from({length: n}, (_, i) => i);
const find = (x) => {
    while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
};
const union = (x, y) => {
    const px = find(x), py = find(y);
    if (px !== py) parent[px] = py;
};

Union-Find (also called Disjoint Set Union) maintains a partition of elements into groups. Two operations: Find (which group does this element belong to?) and Union (merge two groups). With two optimizations — path compression and union by rank — both operations run in effectively constant amortized time. No graph traversal needed for connectivity.

When Union-Find beats BFS/DFS:
- Dynamic connectivity: edges added over time, need to check connectivity after each
- Kruskal's MST: process edges sorted by weight, union endpoints if not already connected
- Detect cycle in undirected graph: if Find(u) === Find(v) before Union(u,v), it's a cycle
- Online vs offline: Union-Find handles streaming edges; BFS/DFS requires the full graph upfront

The Two Optimizations

Union-Find with path compression + union by rank

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank   = new Array(n).fill(0);
        this.count  = n; // number of connected components
    }

    find(x) {
        // Path compression: flatten tree — every node points directly to root
        if (this.parent[x] !== x)
            this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }

    union(x, y) {
        const px = this.find(x), py = this.find(y);
        if (px === py) return false; // already connected
        // Union by rank: attach smaller tree under larger
        if (this.rank[px] < this.rank[py]) this.parent[px] = py;
        else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
        else { this.parent[py] = px; this.rank[px]++; }
        this.count--;
        return true;
    }

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

// Simpler functional version (when rank not needed):
const parent = Array.from({length: n}, (_, i) => i);
const find = (x) => {
    while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
};
const union = (x, y) => {
    const px = find(x), py = find(y);
    if (px !== py) parent[px] = py;
};

Medium

Medium

Medium

Number of Connected Components in an Undirected Graph

Medium

Solve

Kruskal's MST — Union-Find Application

Minimum Spanning Tree (MST): Connects all n nodes with n-1 edges of minimum total weight. No cycles.

Kruskal's algorithm: Sort all edges by weight. Process cheapest edge first. If it connects two different components (union-find check), add it to MST. Skip if both endpoints in same component (would create cycle).

Time: O(E log E) for sorting.

Kruskal's MST with Union-Find

function kruskalMST(n, edges) {
    // edges = [[weight, u, v], ...]
    edges.sort((a, b) => a[0] - b[0]);  // sort by weight
    const parent = Array.from({length: n}, (_, i) => i);
    const rank = new Array(n).fill(0);

    const find = x => {
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    };
    const union = (x, y) => {
        const px = find(x), py = find(y);
        if (px === py) return false;  // same component — would create cycle
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else { parent[py] = px; rank[px]++; }
        return true;
    };

    let totalWeight = 0, edgesUsed = 0;
    const mst = [];
    for (const [w, u, v] of edges) {
        if (union(u, v)) {
            mst.push([u, v, w]);
            totalWeight += w;
            if (++edgesUsed === n - 1) break;  // MST complete
        }
    }
    return { mst, totalWeight, connected: edgesUsed === n - 1 };
}

Min Cost to Connect All Points (MST)

Medium

Solve

Satisfiability of Equality Equations

Medium

Solve

Largest Component Size by Common Factor

Hard

Solve

Union-Find vs BFS/DFS:
- Static graph, one-time query → BFS/DFS is simpler
- Dynamic graph (edges added online) → Union-Find handles streaming
- Cycle detection in undirected → Union-Find is cleaner
- Strongly connected components → Need Tarjan/Kosaraju (DFS), not Union-Find
- Minimum spanning tree → Kruskal = sort edges + Union-Find

Two-pass Union-Find pattern:
1. Process "must be same" constraints → union them
2. Check "must be different" constraints → if same root, contradiction

← DP on Trees Prefix Sum & Difference Array →