Union-Find (Disjoint Set Union): Merging Groups in Almost No Time

Two strangers at a wedding start chatting and discover they have a friend in common. In that instant something quiet happens: two separate friend-circles become one. Keep going around the room — "oh, you know them too?" — and the whole guest list keeps collapsing into fewer and fewer clusters, until you can answer any "are you two connected?" almost without thinking.

That collapsing act has a name. It’s a data structure called union-find (also called disjoint set union, or DSU), and it does exactly two things blindingly fast: tell you whether two things are in the same group, and merge two groups into one. By the end of this article you and I will have built it together — and you’ll understand the one genuinely clever idea that makes it run in almost constant time.

Let’s start nowhere near a computer

Forget arrays for a moment. Picture those friend-circles again, and give each circle a single representative — say, the person who’s been friends with everyone the longest.

Now every question gets easy. To ask "are Priya and Rahul in the same circle?", each of them names their representative. Same representative → same circle. Different → different circles. To merge two circles, you don’t rewrite anybody’s friendships. You just have one representative agree to follow the other. One handshake, and two circles are one.

But how does Priya know her representative? She doesn’t hold the whole circle in her head. She only remembers who introduced her. So she asks that person, who asks the person who introduced them, and so on up the chain until you reach the founder — the one person who was there first and introduces nobody. That founder is the representative.

   founder   ← the representative
      ▲
   Meera       find(Priya):
      ▲          Priya → Meera → founder
   Priya

That’s the entire structure in three moves:

• Everyone remembers just one thing: who’s one step closer to the founder.
• find = follow that chain up to the founder.
• union = point one founder at the other.

Every trick that follows is just about keeping those chains short.

Where you already meet this

Once you see "merge groups, ask who’s connected," it’s everywhere:

• Connected components. Which computers on a network can reach each other; which pixels form one blob in an image.
• Account merging. A fraud system decides two logins are the same human and fuses their histories forever.
• Percolation. Does water seep from the top of a porous slab to the bottom? That’s one big "are these connected?" query.
• Kruskal’s algorithm for the minimum spanning tree — the cheapest set of roads that connects every town.

That last one is worth a closer look, because it shows union-find doing a job nothing else does as neatly. Kruskal’s sorts every road cheapest-first and adds them one by one — but it must refuse any road whose two towns are already connected, or it would build a wasteful loop. How do you check "already connected?" thousands of times, on a graph that’s growing as you go? You don’t re-scan the map. You ask union-find: find(townA) == find(townB)? If yes, skip the road. Union-find is the gatekeeper that keeps Kruskal’s honest, one O(α(n)) question at a time.

What it actually looks like

Drop the people, keep the shape. Number the elements 0, 1, 2, … and give each one a single slot: the index of its parent. A root is a node that points to itself — that’s our founder. Read from any node and follow parents upward, and you always arrive at the root that names its group.

Look at the array at the bottom, because that array is the whole data structure. There’s no tree object, no list of members — just parent[i], the one step toward the root. Node 3’s parent is 1, whose parent is 0, whose parent is 0 (itself, so it’s a root). The three groups are {0, 1, 2, 3}, {4, 5}, and {6}.

Let’s build one, step by step

We’ll build it in small pieces and assemble the full class at the end.

Step 1 — everyone starts alone

Before any merges, every element is its own group of one, so every element is its own root: parent[i] = i. We’ll also keep a running count of how many groups exist, which starts at n.

private final int[] parent;
private int groups;
 
public UnionFind(int n) {
    parent = new int[n];
    for (int i = 0; i < n; i++) {
        parent[i] = i;   // each element is its own root
    }
    groups = n;
}

Step 2 — find: climb to the root

To find a node’s group, follow parents upward until you reach a node that points to itself. That root is the group’s name.

public int find(int x) {
    while (x != parent[x]) {
        x = parent[x];   // climb one step toward the root
    }
    return x;
}

The rule: two nodes are connected exactly when find returns the same root. Not the same parent — the same root. (Hold onto that distinction; it’s the single most common bug, and we’ll come back to it.)

Step 3 — union: link the two roots

To merge two groups, find both roots. If they’re already the same root, there’s nothing to do. Otherwise, point one root at the other — a single pointer change — and drop the group count by one.

public boolean union(int a, int b) {
    int ra = find(a);
    int rb = find(b);
    if (ra == rb) {
        return false;    // already one group — nothing merged
    }
    parent[rb] = ra;     // hang b's root under a's root
    groups--;
    return true;
}

Notice union returns false when the two were already connected. That boolean is quietly powerful — it’s the exact signal Kruskal’s needs to reject a cycle-forming road, and it’s how we’ll detect cycles later.

Step 4 — the trap: tall, skinny trees

Here’s where the naive version bites. Watch what happens if you keep merging fresh elements and always hang the new root on top: union(0,1), union(1,2), union(2,3), union(3,4).

The tree has degenerated into a linked list. Now find(4) has to climb every single node to reach the root. With n elements chained this way, find is O(n) — the structure is no faster than scanning a list, and we’ve gained nothing. Any interviewer worth their salt will feed you exactly this adversarial order to see if your union defends against it.

Step 5 — union by rank: keep trees shallow

The fix costs one extra array and almost no thought: when you link two roots, always hang the shorter tree under the taller one. We track each root’s rank — an upper bound on its height — and let the taller root win.

Attaching a shallow tree under a deep one doesn’t make the deep one any deeper. The only time total height can grow is when you merge two trees of equal rank — and then it grows by exactly one, and the survivor’s rank ticks up.

private final int[] rank;   // an upper bound on each root's height
 
public boolean union(int a, int b) {
    int ra = find(a);
    int rb = find(b);
    if (ra == rb) {
        return false;
    }
    if (rank[ra] < rank[rb]) {   // make ra the taller root
        int tmp = ra;
        ra = rb;
        rb = tmp;
    }
    parent[rb] = ra;             // shorter tree hangs under taller root
    if (rank[ra] == rank[rb]) {
        rank[ra]++;              // a tie: the survivor grew by one
    }
    groups--;
    return true;
}

That single "shorter under taller" rule guarantees a tree of rank r holds at least 2^r nodes — so no tree can ever be taller than log₂ n. Your O(n) chain is now capped at O(log n). Good. But we can do far, far better.

Path compression: make every walk pay for itself

Union by rank keeps trees from growing tall. The second optimization goes on offense: every time you walk up to find a root, you’ve just learned the answer for every node you passed — so re-point them all straight at the root on the way back. The walk shortens the very path it just climbed.

The recursion writes itself. As find returns the root back up the call stack, each level overwrites its own parent pointer with the root:

public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);   // flatten: point straight at the root
    }
    return parent[x];
}

The first find on a deep node still pays the full climb — but it’s the last node that ever will. Every future find on 1, 2, or 3 is now a single hop. The cost of the deep walk is amortized away across all the cheap lookups it enables. This is the whole reason people reach for union-find instead of anything simpler.

Why it’s almost O(1): the inverse-Ackermann story

Robert Tarjan proved in 1975 that with both optimizations, a sequence of m operations on n elements costs O(m · α(n)), where α is the inverse Ackermann function. That deserves an honest, intuitive unpacking, because it’s one of the most quietly astonishing bounds in all of computer science.

Start with what α(n) actually is. The Ackermann function A(n) grows so violently that A(4) already has more digits than there are atoms in the observable universe. Its inverse, α(n), is that growth run backwards — it crawls upward so slowly that for every value of n you will ever encounter in this universe, α(n) ≤ 4. Not "roughly four on average." At most four, full stop. So while O(α(n)) is technically not constant, it is a small constant for all practical inputs — union-find is, for you and every machine you’ll ever touch, effectively O(1) per operation.

Now the intuition for why the two tricks together get there. Two facts do the heavy lifting:

• Union by rank makes ranks precious. Because a rank-r root always sits over at least 2^r nodes, there can be at most n / 2^r nodes of rank r. Ranks are scarce and strictly increase as you climb — a parent always outranks its child.
• Path compression makes every node ambitious. Each time a node is touched by a find, it gets re-pointed to a node of strictly higher rank than its old parent. A node’s parent can only keep leaping to higher and higher ranks a limited number of times before it’s pointing at the top.

Tarjan’s argument groups the possible ranks into a handful of bands — and the number of bands you can climb through is exactly α(n). Each node can only be charged a small amount of work within a band before compression flings it into a higher band, and there are only α(n) bands to cross. Multiply out and the whole sequence costs O(m · α(n)). The magic isn’t in any single find — one lonely find can still cost O(log n). The magic is in the amortization: compression makes every expensive walk buy down the cost of thousands of future ones, and rank guarantees there’s very little total height to pay for in the first place.

Union-find vs the obvious alternatives

The problem union-find solves — dynamic connectivity, where groups merge over time — has simpler-looking rivals. They each lose on one axis. Call n the number of elements and E the number of edges.

The label array answers queries instantly but chokes on merges: fusing two groups means walking one entire group to relabel it. Re-running a graph search is the opposite — cheap to add an edge, but every question re-explores the world. Union-find refuses to specialise: both operations are effectively constant, which is precisely why it’s the tool of choice whenever the groups themselves are still changing.

The complete implementation

Everything above, assembled — the setup, find with path compression, union with rank, connected, a group count, and the cycle check we’ll use next:

package dev.fiveyear.unionfind;
 
public final class UnionFind {
 
    private final int[] parent; // parent[i] = i's parent; a root points to itself
    private final int[] rank;   // an upper bound on the tree's height
    private int groups;         // how many disjoint groups remain
 
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;   // every element starts alone, as its own root
        }
        groups = n;
    }
 
    /** The root that names x's group, flattening the path on the way. */
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);   // path compression
        }
        return parent[x];
    }
 
    /** Merges the two groups; returns false if they were already one. */
    public boolean union(int a, int b) {
        int ra = find(a);
        int rb = find(b);
        if (ra == rb) {
            return false;    // already connected — nothing to merge
        }
        if (rank[ra] < rank[rb]) {   // shorter tree hangs under taller
            int tmp = ra;
            ra = rb;
            rb = tmp;
        }
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) {
            rank[ra]++;      // heights tied, so the survivor grew by one
        }
        groups--;
        return true;
    }
 
    /** True when a and b sit in the same group. */
    public boolean connected(int a, int b) {
        return find(a) == find(b);
    }
 
    /** How many disjoint groups are left. */
    public int count() {
        return groups;
    }
 
    /** True if the n-vertex undirected graph with these edges has a cycle. */
    public static boolean hasCycle(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        for (int[] e : edges) {
            if (!uf.union(e[0], e[1])) {
                return true; // both ends already connected → this edge closes a loop
            }
        }
        return false;
    }
}

And here it is doing the merging we drew, with the outputs it actually produces:

UnionFind uf = new UnionFind(10);
 
uf.union(1, 2);
uf.union(2, 3);            // group {1, 2, 3}
uf.union(4, 5);            // group {4, 5}
 
uf.connected(1, 3);        // true  — same root
uf.connected(1, 4);        // false — different roots
uf.count();                // 7     — three merges out of ten singletons
 
uf.union(3, 4);            // fuse {1,2,3} with {4,5}  → returns true
uf.connected(1, 5);        // true  — now one group
uf.union(1, 5);            // false — already connected, nothing merged
uf.count();                // 6

A classic use: cycle detection in a graph

The hasCycle method above is union-find’s signature party trick. Feed it the edges of an undirected graph one at a time and keep merging their endpoints. The moment union returns false, you’ve hit an edge whose two ends were already in the same group — which means there was already a path between them, and this edge closes a loop.

Edges 1 through 3 each stitch together two different groups. Edge 4 tries to join D and A, but they’re already connected through A → B → C → D. union refuses, returns false, and we’ve found our cycle — no depth-first search, no visited-set bookkeeping, just four constant-time questions.

int[][] triangle = {{0, 1}, {1, 2}, {2, 0}};
UnionFind.hasCycle(3, triangle);          // true  — the third edge closes it
 
int[][] path = {{0, 1}, {1, 2}, {2, 3}};
UnionFind.hasCycle(4, path);              // false — a straight path, no loop
 
int[][] withBackEdge = {{0, 1}, {2, 3}, {3, 4}, {4, 2}};
UnionFind.hasCycle(5, withBackEdge);      // true  — 4-2 loops back into {2,3,4}

The interview corner

Union-find looks tiny, which is exactly why interviewers love it — the whole test is whether you know the two optimizations and the one classic bug. Here’s how to walk in ready.

Ask these before you write a line:

• "Is the structure dynamic — do unions arrive over time — or is the whole graph known up front?" If it’s static and you only need connectivity once, a single DFS may be simpler. Union-find earns its keep when merges keep coming.
• "Will I ever need to split a group or delete an edge?" If yes, plain union-find is the wrong tool — it can’t cheaply undo. Flag it early.
• "What are the elements — dense integers 0…n-1, or arbitrary keys?" The array version needs small integers; arbitrary keys need a HashMap from key to key, or an id-mapping pass first.

The follow-up ladder — where a strong candidate keeps climbing:

1. "Also report each group’s size." Keep a size[] indexed by root; on union, add the smaller into the larger. O(1) to read any group’s size.
2. "Union by size or by rank — does it matter?" Same asymptotics. Size counts nodes, rank bounds height; size is easier to maintain and doubles as useful data, so many people prefer it.
3. "Support undo of the last union." Drop path compression (it scrambles too many pointers to reverse), keep union by rank, and push (root, oldRank) on a stack — rollback pops and restores. This "rollback DSU" is the backbone of offline dynamic connectivity.
4. "n doesn’t fit in memory / it’s distributed." The array shards trivially by id, but cross-shard unions need a coordinator; in practice you batch the edges and run union-find offline, the way MapReduce computes connected components.
5. "Detect a cycle in a directed graph with it." You can’t — union-find only sees undirected connectivity. Directed cycles need DFS colours or Tarjan’s strongly-connected-components, a different traversal entirely. (See the graph walk in Dijkstra’s algorithm.)

Three mistakes that fail the round:

• Comparing parents instead of roots. parent[a] == parent[b] is not "same group" — two nodes deep in one tree can have different immediate parents. Always compare find(a) == find(b).
• Skipping the optimizations. Without rank and compression, an adversarial union order builds an O(n) chain and your "fast" structure crawls. Interviewers hand you that exact input on purpose.
• Corrupting the invariants. Bumping rank on every union (it should rise only on a tie) or decrementing the group count on a no-op union quietly rots the height bound and the component count. Only change state when a real merge happens.

Where to go from here

You now own the core: a group is a tree, its root is the name, find climbs, union links roots — and rank plus compression keep the climb flat. Three natural next stops:

• Kruskal’s minimum spanning tree — put a sort in front of the cycle check you just built and you have the cheapest network that connects every node. Union-find is its engine.
• Union by size + small-to-large merging — the "DSU on tree" pattern that answers subtree queries offline in O(n log n).
• Rollback DSU and link-cut trees — what you graduate to when edges must come and go, and the one-way street of plain union-find isn’t enough.

Next time you discover a mutual friend with a stranger, you’ll know what just happened under the hood: two roots shook hands, a single pointer changed, and two circles quietly became one.