Union-find (disjoint set union)

intermediateCommon atGoogleAmazonMetaAnthropicRead firstArraysGraph representationPractise in the Sandbox →

Union-find (also called disjoint set union, DSU) keeps items in non-overlapping groups. It supports two operations: find(x), which returns a representative of x’s group, and union(a, b), which merges two groups. Each group is a tree of parent pointers stored in one array. With union by size (or rank) and path compression, both operations cost O(α(n)) amortized, where α is the inverse Ackermann function: at most 4 for any realistic n. It can merge groups but cannot split them.

The idea in plain words

Picture a school where every club has a president. To find out whether two students are in the same club, you don’t compare membership lists. You ask each student “who’s your president?”, and compare the answers.

That’s union-find. Every group has one root (the president). Each item stores a single pointer to its parent, someone closer to the root. find(x) follows parents until it reaches a node that is its own parent. Two items are connected exactly when they find the same root.

To merge two clubs, you don’t touch the members. You make one president report to the other: a single pointer write.

The catch is the chain of command. If clubs merge badly, a student might have to ask their parent, who asks theirs, who asks theirs, and so on: a long chain. Two tricks keep chains short:

• Union by size (or rank): when merging, the smaller tree goes under the bigger tree’s root. A node only gets one level deeper when its group at least doubles, so no node is ever more than log₂ n levels deep.
• Path compression: after find(x) discovers the root, repoint every node it passed straight at the root. The next lookup from any of them is one hop.

See it

Union pairs and find roots. The forest on top is what the array below means; the array is all that’s stored. Press worst-case chain to build the 10-deep chain that naive merging produces, then turn path compression on and find(0) twice.

Union-find: a forest of parent pointers

interactive

ab

operateunion(a, b)find(a)worst-case chainreset

the forest (each tree is one set; arrows point up to the parent)

parent[ ]: the only thing actually stored

0

1

2

3

4

5

6

7

8

9

0123456789

sets10

size (roots)0:1 1:1 2:1 3:1 4:1 5:1 6:1 7:1 8:1 9:1

current / re-linkedpath climbedcompressedroot

10 elements, each in its own set: everyone is their own parent. Union two elements, or find one's root.

↺◀▶ Play▶1 / 1

Operation log

10 sets. Try union(3,7), union(1,3), union(7,9), then find(9).

Things to try:

• With union by size, do union(0,1), union(2,3), union(0,2). Then union a single element into that group: it always goes under the big root.
• Switch to naive and compression off, build the chain, and find(0) twice: 9 hops both times. Turn compression on and do it again.
• Union two elements that are already connected. That “already joined” answer is how union-find detects cycles.

When to reach for it

The problem says…	Why union-find fits
“are a and b connected?” while edges are only added	Each new edge is a union; each question is two finds.
“how many groups / components” after merges	Keep a counter; every successful union decrements it.
“does this edge create a cycle?” (undirected)	The endpoints already share a root.
“merge accounts / records that share an attribute”	Union each record with the first record seen for that attribute.
Kruskal’s minimum spanning tree	Take edges cheapest first; skip any whose endpoints are already connected. See MST.
“equivalence” constraints like a == b, b == c, a != c	Union all the equalities, then check the inequalities.

When it doesn't fit

Union-find can’t delete an edge or split a group, and it can’t tell you the path between two items, only whether one exists. If edges are removed, consider processing operations in reverse (removals become unions), or use BFS / DFS on a graph. For a static graph where you only need components once, a single BFS/DFS is just as fast and simpler.

How it works

1. Find: from x, follow parent[x] until you reach a node whose parent is itself. That’s the root.
2. Compress: walk the same path again (or on the way back out of the recursion) and set each node’s parent to the root.
3. Union: find both roots. If they’re equal, the items are already together; return false. Otherwise hang the smaller tree’s root under the bigger one and add the sizes.

Python

dsu.py

class DSU:
    """Disjoint set union with path compression + union by size: ~O(1) amortized per op."""

    def __init__(self, n: int) -> None:
        self.parent = list(range(n))       # everyone starts as their own root
        self.size = [1] * n                # only meaningful at roots
        self.sets = n

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            # 1. climb to the root, 2. on the way back point every node straight at it.
            #    Union by size keeps depth <= log2(n), so this recursion stays shallow.
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                   # already in the same set
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra                # 3. hang the smaller tree under the bigger one
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.sets -= 1
        return True


def count_components(n: int, edges: list[tuple[int, int]]) -> int:
    d = DSU(n)
    for a, b in edges:
        d.union(a, b)
    return d.sets


if __name__ == "__main__":
    assert count_components(5, [(0, 1), (1, 2), (3, 4)]) == 2
    assert count_components(4, []) == 4
    d = DSU(6)
    assert d.union(0, 1) and d.union(2, 3) and d.union(1, 3)
    assert not d.union(0, 2)               # already connected through 1-3
    assert d.find(0) == d.find(3) and d.size[d.find(0)] == 4
    assert d.find(4) != d.find(0)
    print("ok")

TypeScript

dsu.ts

import assert from "node:assert/strict";

/** Disjoint set union with path compression + union by size: ~O(1) amortized per op. */
export class DSU {
  readonly parent: number[];
  readonly size: number[];
  sets: number;

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i); // everyone starts as their own root
    this.size = new Array<number>(n).fill(1); // only meaningful at roots
    this.sets = n;
  }

  find(x: number): number {
    let root = x;
    while (this.parent[root] !== root) root = this.parent[root]; // 1. climb to the root
    while (this.parent[x] !== root) { // 2. second pass: point every node on the path at it
      const next = this.parent[x];
      this.parent[x] = root;
      x = next;
    }
    return root;
  }

  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false; // already in the same set
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra]; // 3. smaller tree under bigger
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.sets--;
    return true;
  }
}

export function countComponents(n: number, edges: [number, number][]): number {
  const d = new DSU(n);
  for (const [a, b] of edges) d.union(a, b);
  return d.sets;
}

assert.equal(countComponents(5, [[0, 1], [1, 2], [3, 4]]), 2);
assert.equal(countComponents(4, []), 4);
const d = new DSU(6);
assert.ok(d.union(0, 1) && d.union(2, 3) && d.union(1, 3));
assert.equal(d.union(0, 2), false); // already connected through 1-3
assert.equal(d.size[d.find(0)], 4);
assert.notEqual(d.find(4), d.find(0));
console.log("ok");

C#

dsu.cs

if (CountComponents(5, [(0, 1), (1, 2), (3, 4)]) != 2) throw new Exception("two components");
if (CountComponents(4, []) != 4) throw new Exception("no edges");
var d = new Dsu(6);
if (!(d.Union(0, 1) && d.Union(2, 3) && d.Union(1, 3))) throw new Exception("unions");
if (d.Union(0, 2)) throw new Exception("0 and 2 are already connected through 1-3");
if (d.Find(0) != d.Find(3) || d.Find(4) == d.Find(0)) throw new Exception("find");
Console.WriteLine("ok");

static int CountComponents(int n, (int A, int B)[] edges)
{
    var d = new Dsu(n);
    foreach (var (a, b) in edges) d.Union(a, b);
    return d.Sets;
}

// Disjoint set union with path compression + union by size: ~O(1) amortized per op.
class Dsu
{
    private readonly int[] parent, size;
    public int Sets { get; private set; }

    public Dsu(int n)
    {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } // everyone is their own root
        Sets = n;
    }

    public int Find(int x)
    {
        int root = x;
        while (parent[root] != root) root = parent[root];          // 1. climb to the root
        while (parent[x] != root)                                   // 2. second pass: point every
        {                                                           //    node on the path at it
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    public bool Union(int a, int b)
    {
        int ra = Find(a), rb = Find(b);
        if (ra == rb) return false;                                 // already in the same set
        if (size[ra] < size[rb]) (ra, rb) = (rb, ra);               // 3. smaller tree under bigger
        parent[rb] = ra;
        size[ra] += size[rb];
        Sets--;
        return true;
    }
}

A classic use: detecting a cycle

Feed edges of an undirected graph in order. The first edge whose endpoints already share a root closes a cycle. This variant uses path halving (each node on the way up jumps to its grandparent), a one-loop alternative to full compression with the same guarantee.

Python

cycle.py

def first_cycle_edge(n: int, edges: list[tuple[int, int]]) -> tuple[int, int] | None:
    """Undirected graph: the first edge whose endpoints are already connected, or None."""
    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # path halving: skip a level as you climb
            x = parent[x]
        return x

    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:                        # 1. same set already: this edge closes a loop
            return (a, b)
        parent[ra] = rb                     # 2. otherwise merge the two components
    return None                             # 3. no edge closed a loop: it's a forest


if __name__ == "__main__":
    assert first_cycle_edge(4, [(0, 1), (1, 2), (2, 0), (2, 3)]) == (2, 0)
    assert first_cycle_edge(4, [(0, 1), (2, 3), (1, 2)]) is None
    assert first_cycle_edge(2, [(0, 1), (1, 0)]) == (1, 0)   # a parallel edge is a 2-cycle
    print("ok")

TypeScript

cycle.ts

import assert from "node:assert/strict";

/** Undirected graph: the first edge whose endpoints are already connected, or null. */
export function firstCycleEdge(n: number, edges: [number, number][]): [number, number] | null {
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]]; // path halving: skip a level as you climb
      x = parent[x];
    }
    return x;
  };
  for (const [a, b] of edges) {
    const ra = find(a), rb = find(b);
    if (ra === rb) return [a, b]; // 1. same set already: this edge closes a loop
    parent[ra] = rb; // 2. otherwise merge the two components
  }
  return null; // 3. no edge closed a loop: it's a forest
}

assert.deepEqual(firstCycleEdge(4, [[0, 1], [1, 2], [2, 0], [2, 3]]), [2, 0]);
assert.equal(firstCycleEdge(4, [[0, 1], [2, 3], [1, 2]]), null);
assert.deepEqual(firstCycleEdge(2, [[0, 1], [1, 0]]), [1, 0]); // a parallel edge is a 2-cycle
console.log("ok");

C#

cycle.cs

if (FirstCycleEdge(4, [(0, 1), (1, 2), (2, 0), (2, 3)]) != (2, 0)) throw new Exception("triangle");
if (FirstCycleEdge(4, [(0, 1), (2, 3), (1, 2)]) is not null) throw new Exception("forest");
if (FirstCycleEdge(2, [(0, 1), (1, 0)]) != (1, 0)) throw new Exception("parallel edge");
Console.WriteLine("ok");

// Undirected graph: the first edge whose endpoints are already connected, or null.
static (int, int)? FirstCycleEdge(int n, (int A, int B)[] edges)
{
    var parent = Enumerable.Range(0, n).ToArray();
    int Find(int x)
    {
        while (parent[x] != x)
        {
            parent[x] = parent[parent[x]];          // path halving: skip a level as you climb
            x = parent[x];
        }
        return x;
    }
    foreach (var (a, b) in edges)
    {
        int ra = Find(a), rb = Find(b);
        if (ra == rb) return (a, b);                // 1. same set already: this edge closes a loop
        parent[ra] = rb;                            // 2. otherwise merge the two components
    }
    return null;                                    // 3. no edge closed a loop: it's a forest
}

Size or rank?

Rank is an upper bound on a tree’s height; size is its node count. Both give the same O(log n) depth bound and the same α(n) bound with compression. Size is usually more useful, because you often want “how big is this group?” anyway. Just don’t mix them up mid-implementation.

What it costs

Strategy	find / union (amortized)	Why
Naive linking, no compression	O(n) worst case	adversarial merges build a chain
Union by size or rank only	O(log n)	a node gets deeper only when its group doubles
Path compression only	O(log n) amortized	each long path is flattened after it’s paid for once
Both	O(α(n))	Tarjan’s bound; α(n) ≤ 4 for n < 2^65536
Space	O(n)	one parent array plus one size/rank array

So m operations on n items cost O((n + m)·α(n)): linear for every practical purpose. Interviewers accept “amortized nearly O(1)”, but say amortized: a single find can still walk O(log n) nodes.

The difference only shows up on bad input. Drag n and switch the workload:

Total pointer hops for 1000 unions + 1000 finds

drag the slider

n = 1000

Naive link, no compression

995,492

Path compression only

1,998

Union by size only

1,873

Size + compression

1,873

On the adversarial order, naive linking builds an n-deep chain and every find pays for it: roughly n² hops. Either fix alone tames it; together they give O(α(n)) amortized per operation, where α (inverse Ackermann) is at most 4 for any n you will ever store. On random pairs even the naive version is fine, which is why bugs here hide until real data arrives.

Variations you’ll meet

• Size tracking. size[find(x)] is the size of x’s group, for free once you union by size.
• Mapping keys to indices. Items are strings or coordinates? Keep a dict from item to index (assign indices lazily as items appear), or use a dict as the parent map directly.
• Weighted / potential union-find. Store each node’s offset relative to its parent (e.g. x = y + 3, or a ratio). Find accumulates offsets along the path; compression must fold them in. Used for “evaluate division”-style equation systems.
• Union-find with rollback. Skip path compression, keep union by rank, and push every change on a stack so you can undo the last union. Used in offline algorithms.
• Offline reversal. For “remove edges one by one and report components”, add all edges in reverse order instead.
• Kruskal’s MST. Sort edges by weight; union-find decides which ones join two different trees.

Pitfalls

• Comparing parents instead of roots. parent[a] == parent[b] is wrong; use find(a) == find(b).
• Linking non-roots. parent[a] = b instead of parent[find(a)] = find(b) corrupts the forest.
• Updating size at the wrong node. Size is only valid at roots. Add the child root’s size to the new root.
• Recursion depth. Recursive find on a naive (unbalanced) forest can be n deep. Use union by size, or an iterative find.
• Forgetting the “already joined” case when counting components or detecting cycles.
• Expecting deletion to work. It doesn’t. Re-read the problem: is it really insert-only?

In the interview

• Say why you chose it: “Edges only get added and I need connectivity queries in between, so union-find beats re-running BFS each time.”
• State both optimizations and the bound: “Union by size plus path compression: amortized inverse-Ackermann, effectively constant.”
• Mention what it can’t do (split, path reconstruction) before the interviewer asks.
• Expect follow-ups: “How many groups are there right now?” (a counter decremented on each successful union), “Now items are strings” (an id map), “What if edges can be removed?” (offline reversal, or a different structure), “Is it thread-safe?” (no; finds write during compression).

Check yourself

Check yourself

pick one

With union by size, why can no node be more than log₂ n levels deep?

ABecause path compression flattens everythingBA node only moves one level deeper when its tree is merged under a tree at least as big, so its group size at least doubles each time; that can happen at most log₂ n timesCBecause the trees are binaryDBecause union always attaches to the root

Check yourself

pick one

You union edges (0,1), (1,2), (2,3) and then process (3,0). What does union(3, 0) report, and what does that mean?

AIt merges two groupsBFalse: 3 and 0 already share a root, so edge (3,0) closes a cycleCAn error, because 0 was already mergedDTrue: it updates the root

Check yourself

pick one

Edges are added and removed over time, and you must answer 'connected?' after each change. Is plain union-find enough?

AYes, union-find handles bothBYes, if you use path compressionCNo: union-find can merge groups but cannot split them when an edge is removedDNo: union-find is only for trees

Practice on your own

These are classic textbook exercises, not gym questions:

• Count the connected groups (“provinces”) in an adjacency matrix of friendships.
• Merge user accounts that share at least one email address.
• Check whether equations like a==b, b!=c, c==a can all hold at once.
• Kruskal’s algorithm for a minimum spanning tree.
• Given a graph that is a tree plus one extra edge, find that edge (the cycle sample, generalized).

Go deeper

• Sedgewick and Wayne, Algorithms §1.5, Case Study: Union-Find: quick-find, quick-union, weighted quick-union, path compression, with measurements.
• cp-algorithms: Disjoint Set Union: rank vs size, weighted DSU, rollback, offline applications.
• CLRS, ch. 19 (ch. 21 in older editions) “Data Structures for Disjoint Sets”: the α(n) analysis.
• Tarjan, R. E. (1975), “Efficiency of a Good But Not Linear Set Union Algorithm”, Journal of the ACM 22(2): the original inverse-Ackermann bound.

Related

Graph representationEdge lists are union-find's natural input.

Minimum spanning treesKruskal's algorithm runs on union-find.

Breadth-first searchThe alternative for static graphs and paths.

Grids and matricesCells as nodes, neighbors as edges.