Union-find (disjoint set)

How does Union-find (disjoint set) work?

Union-find, disjoint set and DSU (disjoint set union) name the same structure.

Each element starts as its own group. Its parent pointer points at itself.

find walks up the parent chain until it reaches a root. The root is the group's name.

union takes two elements, finds both roots, and hangs one under the other. One call merges two groups.

Path compression rewrites every node on the walk to point straight at the root. The next find is one hop.

Union by rank hangs the shorter tree under the taller one. That stops the chains from growing.

With both, a find or a union costs near constant time. Nothing here needs the edges kept.

Sources: Wikipedia: Disjoint-set data structure, Tarjan (1975), Efficiency of a good but not linear set union algorithm

1. [0, 1, 2, 3, 4]Five elements, five groups. Each one is its own parent.
2. [0, 0, 2, 3, 4]union(0, 1) hangs 1 under 0. Two elements now share a root.
3. [0, 0, 2, 2, 4]union(2, 3) hangs 3 under 2. A second group forms.
4. [0, 0, 0, 2, 4]union(1, 2) finds roots 0 and 2. Root 2 hangs under root 0.
5. [0, 0, 0, 0, 4]find(3) walks 3 to 2 to 0. Compression points 3 straight at 0.

class UnionFind {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }
    find(x) {
        if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x, y) {
        const rx = this.find(x), ry = this.find(y);
        if (rx === ry) return false;
        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]++; }
        return true;
    }
}

class UnionFind {
    private parent: number[];
    private rank: number[];

    constructor(n: number) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array<number>(n).fill(0);
    }

    find(x: number): number {
        if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }

    union(x: number, y: number): boolean {
        const rx = this.find(x);
        const ry = this.find(y);
        if (rx === ry) return false;
        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]++; }
        return true;
    }
}

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

class UnionFind {
    private array $parent;
    private array $rank;

    public function __construct(int $n) {
        $this->parent = range(0, $n - 1);
        $this->rank = array_fill(0, $n, 0);
    }

    public function find(int $x): int {
        if ($this->parent[$x] !== $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    public function union(int $x, int $y): bool {
        [$rx, $ry] = [$this->find($x), $this->find($y)];
        if ($rx === $ry) return false;
        if ($this->rank[$rx] < $this->rank[$ry]) [$rx, $ry] = [$ry, $rx];
        $this->parent[$ry] = $rx;
        if ($this->rank[$rx] === $this->rank[$ry]) $this->rank[$rx]++;
        return true;
    }
}

    public static class UnionFind {
        private final int[] parent;
        private final int[] rank;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }

        public int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        public boolean union(int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx == ry) return false;
            if (rank[rx] < rank[ry]) parent[rx] = ry;
            else if (rank[rx] > rank[ry]) parent[ry] = rx;
            else { parent[ry] = rx; rank[rx]++; }
            return true;
        }
    }

    public class UnionFind {
        private readonly int[] parent;
        private readonly int[] rank;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }

        public int Find(int x) {
            if (parent[x] != x) parent[x] = Find(parent[x]);
            return parent[x];
        }

        public bool Union(int x, int y) {
            int rx = Find(x), ry = Find(y);
            if (rx == ry) return false;
            if (rank[rx] < rank[ry]) parent[rx] = ry;
            else if (rank[rx] > rank[ry]) parent[ry] = rx;
            else { parent[ry] = rx; rank[rx]++; }
            return true;
        }
    }

A worked example of Union-find (disjoint set)

Redundant connection

You get a graph that was a tree, plus one extra edge. Find the edge that closes a cycle.

Edges arrive in order. Return the last one joining two nodes already connected.

Walk the edges in order and union each one.

When both ends already share a root, the edge adds nothing. It closes a cycle.

Keep the last such edge. That is the answer.

function findRedundantConnection(edges) {
    const parent = Array.from({ length: edges.length + 1 }, (_, i) => i);

    function find(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    }

    let answer = [];
    for (const [a, b] of edges) {
        const rootA = find(a);
        const rootB = find(b);
        if (rootA === rootB) {
            answer = [a, b]; // both ends were already connected
        } else {
            parent[rootA] = rootB;
        }
    }

    return answer;
}

When should you use Union-find (disjoint set)?

Use Union-find (disjoint set) when the problem statement says “are these two in the same group”, “merge/union facts arrive one at a time” or “dynamic connectivity as edges are added”. A solution built on it usually runs in near O(1) per op.

• •are these two in the same group
• •merge/union facts arrive one at a time
• •dynamic connectivity as edges are added
• •account/friend merging over time
• •adding this edge would create a cycle

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Union-find (disjoint set) confused with?

Union-find (disjoint set) is most often confused with Connected components, Graph BFS / DFS, Topological sort and Hash set / map.

• Connected components: Flood fill counts groups in a graph that is already complete. Union-find answers while the edges are still arriving.
• Graph BFS / DFS: A traversal visits neighbours, so it needs an adjacency list. Union-find never stores the edges at all.
• Topological sort: Topological order needs directed edges and a DAG. Union-find treats every edge as undirected.
• Hash set / map: A map groups by a key you already know. Union-find discovers the groups as facts merge them.

Common mistakes with Union-find (disjoint set)

• Comparing elements instead of roots

  Two elements can sit in one group with different parents. Compare find(a) with find(b).

• Union without find

  Writing parent[a] = b joins two elements, not two groups. Always hang one root under the other.

• Skipping path compression

  Without it a chain can grow to n links. A single find then costs O(n).

• Sizing the array by edge count

  The array is indexed by element, not by edge. An off-by-one here reads undefined for the last node.

Which interview problems use Union-find (disjoint set)?

Interview problems solved with Union-find (disjoint set) include Number of provinces, Redundant connection, Accounts merge, Number of islands, Most stones removed, Satisfiability of equality equations, Smallest string with swaps and Min cost to connect all points.

• Number of provinces: Union every connected pair, then count the distinct roots.
• Redundant connection: The first edge whose two ends already share a root.
• Accounts merge: Emails link accounts. Union on a shared email, then group by root.
• Number of islands: Union neighbouring land cells. Useful when the grid arrives in pieces.
• Most stones removed: Stones sharing a row or a column belong to one group.
• Satisfiability of equality equations: Union the equals first. Then test every not-equals against the roots.
• Smallest string with swaps: Swappable indices form a group. Sort the letters inside each group.
• Min cost to connect all points: Kruskal's algorithm: sort edges by cost, keep each edge whose ends have different roots.

What is the time and space complexity of Union-find (disjoint set)?

The target complexity of Union-find (disjoint set) is near O(1) per op.

n up to 1e6 elements with m interleaved queries gives O(m alpha(n)). Alpha is under 5 for any n you will meet.