Union-Find

Updated Nov 16, 2026 · 5 min read
On this page

    Connections keep arriving: "user 3 and user 7 are the same person", "server A can now reach server B", "these two accounts share an email". After each one you need to answer "are X and Y in the same group?" or "how many groups are there now?". Re-running a DFS over the whole graph after every new edge is far too slow. Union-find keeps the groups up to date as edges arrive, at almost O(1) per operation.

    This page covers both the data structure and the pattern: the Union-Find problems in the Problems section build on it directly.

    How it works

    Every group is a tree with a representative

    Each element points to a parent; following parents leads to the root, which names the group. Two elements are connected exactly when they reach the same root.
    Each element points to a parent; following parents leads to the root, which names the group. Two elements are connected exactly when they reach the same root.

    Union-find (also called a disjoint set union, or DSU) keeps a parent array. At the start every element is its own parent: n groups of one. Two operations:

    • find(x): follow parent pointers until you reach an element that is its own parent. That root is the group's representative.
    • union(a, b): find both roots; if they differ, make one root point to the other. The two groups are now one.

    "Are a and b connected?" is just find(a) == find(b).

    Union by size

    To merge, attach the root of the smaller tree under the root of the larger one, so trees stay shallow.
    To merge, attach the root of the smaller tree under the root of the larger one, so trees stay shallow.

    If you always attach the smaller tree under the larger, no element's depth can grow beyond about log₂ n, because every time an element gets one level deeper, its group at least doubles in size. Track size[root] and compare.

    Path compression

    After find walks a long chain, point the nodes it passed directly at the root so later finds take one step.
    After find walks a long chain, point the nodes it passed directly at the root so later finds take one step.

    While find walks to the root, re-point the nodes it passes at (or closer to) the root. A simple version is path halving: parent[x] = parent[parent[x]] at each step. With both tricks the cost per operation is "inverse Ackermann", which is at most 4 or 5 for any input you'll ever see. In interviews, say "nearly O(1), amortized".

    Operations and costs

    OperationNo tricksUnion by size + path compression
    findO(n) worst casenearly O(1) amortized
    unionO(n) worst casenearly O(1) amortized
    connected(a, b)O(n)nearly O(1)
    Count groupsO(1) if you keep a counterO(1)
    MemoryO(n)O(n)

    When to reach for it

    • Edges arrive over time and you need connectivity after each one (dynamic connectivity, Number of Islands II).
    • Count groups after a set of merges (connected components, friend circles, provinces).
    • Detect a cycle in an undirected graph: if both ends of a new edge already have the same root, that edge closes a cycle (Redundant Connection, Graph Valid Tree).
    • Group items by shared attributes: union every pair that shares something, then collect each root's members (Accounts Merge).
    • Kruskal's minimum spanning tree: sort edges by weight and add each one unless it would close a cycle.

    Union-find or DFS? If the graph is fixed and you need components once, DFS is just as good. Union-find wins when edges keep arriving, or when you only need "same group?" answers and not paths. It can't remove edges or tell you the path between two nodes.

    Example

    A reusable class with union by size and path halving:

    class UnionFind:
        def __init__(self, n):
            self.parent = list(range(n))
            self.size = [1] * n
            self.groups = n
    
        def find(self, x):
            while self.parent[x] != x:
                self.parent[x] = self.parent[self.parent[x]]   # path halving
                x = self.parent[x]
            return x
    
        def union(self, a, b):
            ra, rb = self.find(a), self.find(b)
            if ra == rb:
                return False                 # already connected: this edge closes a cycle
            if self.size[ra] < self.size[rb]:
                ra, rb = rb, ra
            self.parent[rb] = ra             # attach the smaller tree under the larger
            self.size[ra] += self.size[rb]
            self.groups -= 1
            return True
    class UnionFind {
        private final int[] parent, size;
        int groups;
    
        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
            groups = n;
        }
        int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        boolean union(int a, int b) {
            int ra = find(a), rb = find(b);
            if (ra == rb) return false;
            if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
            parent[rb] = ra;
            size[ra] += size[rb];
            groups--;
            return true;
        }
    }
    class UnionFind {
        vector<int> parent, sz;
    public:
        int groups;
        UnionFind(int n) : parent(n), sz(n, 1), groups(n) {
            iota(parent.begin(), parent.end(), 0);
        }
        int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        bool unite(int a, int b) {           // "union" is a C++ keyword
            int ra = find(a), rb = find(b);
            if (ra == rb) return false;
            if (sz[ra] < sz[rb]) swap(ra, rb);
            parent[rb] = ra;
            sz[ra] += sz[rb];
            groups--;
            return true;
        }
    };
    type UnionFind struct {
        parent, size []int
        groups       int
    }
    
    func NewUnionFind(n int) *UnionFind {
        uf := &UnionFind{parent: make([]int, n), size: make([]int, n), groups: n}
        for i := range uf.parent {
            uf.parent[i] = i
            uf.size[i] = 1
        }
        return uf
    }
    
    func (uf *UnionFind) Find(x int) int {
        for uf.parent[x] != x {
            uf.parent[x] = uf.parent[uf.parent[x]]
            x = uf.parent[x]
        }
        return x
    }
    
    func (uf *UnionFind) Union(a, b int) bool {
        ra, rb := uf.Find(a), uf.Find(b)
        if ra == rb {
            return false
        }
        if uf.size[ra] < uf.size[rb] {
            ra, rb = rb, ra
        }
        uf.parent[rb] = ra
        uf.size[ra] += uf.size[rb]
        uf.groups--
        return true
    }

    Time: nearly O(1) per operation, so O(n + m) for n elements and m unions in practice. Space: O(n).

    With 6 elements and unions (1,0), (2,0), (3,2), (5,4) there are 2 groups and find(3) != find(5). union(3, 5) merges them into one group; a later union(1, 4) returns false because 1 and 4 are already connected, which is exactly the "this edge closes a cycle" signal.

    Common mistakes

    • Comparing elements instead of roots. parent[a] == parent[b] is wrong; compare find(a) == find(b).
    • Linking the elements, not the roots. parent[a] = b can break the structure; always link find(a)'s root to find(b)'s root.
    • Updating size on the wrong root. Add the smaller tree's size to the root that stays a root.
    • Forgetting the group counter when the problem asks "how many groups now?", then recounting in O(n) each time.
    • Non-integer items. Map strings (like emails) to integer ids with a hash map first, or use a dictionary-based parent map.
    • Expecting deletions or paths. Union-find can't split groups or return the path between two nodes.

    Say this in the interview

    • "Edges arrive one at a time and I only need 'are these connected?', so union-find fits: nearly O(1) per operation with union by size and path compression."
    • "If union returns false, both ends were already in the same group, so this edge would close a cycle."
    • "I'll keep a group counter that drops by one on every successful union, so the number of components is always O(1) to read."

    Used in