Union-find (disjoint set union)

Lesson · 11 min read · Graphs · Union-find and spanning trees

Keep track of groups as connections arrive, answering "are these two connected?" in nearly constant time.

Groups that only ever merge

Traversals answer connectivity questions about a graph that is already built. Many problems instead add connections one at a time and ask, after each, whether two items are now connected, or how many groups there are, or whether the new connection closed a loop. Re-running a search after every edge costs O(n + m) each time. Union-find answers each question in almost constant time.

It supports two operations on a collection of disjoint groups:

find(x): the representative (root) of x's group. Two items are connected exactly when their roots are equal.
union(a, b): merge the groups containing a and b.

A forest of parent pointers

Each group is stored as a tree in which every node points to its parent, and the root points to itself. find follows pointers up to the root; union points one root at the other. Two refinements keep the trees flat:

Union by size: attach the smaller tree under the larger one, so no tree grows taller than log₂ n.
Path compression: after a find, point every node passed on the way directly at the root, so the next lookup is one step.

Together they make each operation run in amortised O(α(n)) time, where α is the inverse Ackermann function: below 5 for any n that fits in the universe.

Union-find

find(x)

If parent[x] ≠ x, set parent[x] = find(parent[x]) (path compression).
Return parent[x].

union(a, b)

Let ra = find(a), rb = find(b). If equal, return false: already connected.
Attach the root of the smaller group under the other, add the sizes, return true.

Step by step

Six nodes, edges arriving in the order 0–1, 2–3, 1–3, 0–2, 4–5, 3–4. The tag on each root is its group size.

Union-find with union by size and path compression. Arrows point from a node to its parent.

Step 1 / 7

groups6
Every node starts as its own root: n separate groups. An arrow points from a node to its parent.
Step 2 / 7

groups5
Edge 0–1: roots 0 and 1 differ. Attach the smaller tree (root 1) under the larger (root 0).
Step 3 / 7

groups4
Edge 2–3: roots 2 and 3 differ. Attach the smaller tree (root 3) under the larger (root 2).
Step 4 / 7

groups3
Edge 1–3: roots 0 and 2 differ. Attach the smaller tree (root 2) under the larger (root 0).
Step 5 / 7

groups3
Edge 0–2: find(0) = find(2) = 0. They are already in the same group, so this edge would close a cycle.
Step 6 / 7

groups2
Edge 4–5: roots 4 and 5 differ. Attach the smaller tree (root 5) under the larger (root 4).
Step 7 / 7

groups1
Edge 3–4: roots 0 and 4 differ. Attach the smaller tree (root 4) under the larger (root 0). Path compression also re-pointed 3 at its root. 1 group remains.

root that absorbed a groupboth ends already connected

The fourth edge, 0–2, is the interesting one: both ends already have root 0, so it adds nothing to connectivity. In a graph it is exactly the edge that closes a cycle.

Implementation

The problem at the end of this module adds edges until one closes a cycle, which is the most direct use of union returning false. In six languages:

def redundant_edge(edges):
    parent = list(range(len(edges) + 1))     # nodes are 1..n
    size = [1] * (len(edges) + 1)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]    # path halving
            x = parent[x]
        return x

    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            return [a, b]                    # already connected: this edge closes the cycle
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra                      # smaller tree under the larger
        size[ra] += size[rb]
    return []

#include <numeric>
#include <utility>
#include <vector>

std::vector<int> solve(const std::vector<std::vector<int>>& edges) {
    const int n = edges.size();
    std::vector<int> parent(n + 1), size(n + 1, 1);       // nodes are 1..n
    std::iota(parent.begin(), parent.end(), 0);
    auto find = [&](int x) {
        while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }   // path halving
        return x;
    };
    for (const auto& e : edges) {
        int ra = find(e[0]), rb = find(e[1]);
        if (ra == rb) return {e[0], e[1]};                // closes the cycle
        if (size[ra] < size[rb]) std::swap(ra, rb);
        parent[rb] = ra;
        size[ra] += size[rb];
    }
    return {};
}

class Solution {
    private int[] parent;

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

    public int[] redundantEdge(int[][] edges) {
        int n = edges.length;
        parent = new int[n + 1];                            // nodes are 1..n
        int[] size = new int[n + 1];
        for (int i = 0; i <= n; i++) { parent[i] = i; size[i] = 1; }
        for (int[] e : edges) {
            int ra = find(e[0]), rb = find(e[1]);
            if (ra == rb) return new int[]{e[0], e[1]};     // closes the cycle
            if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
            parent[rb] = ra;
            size[ra] += size[rb];
        }
        return new int[0];
    }
}

function redundantEdge(edges) {
  const parent = Array.from({ length: edges.length + 1 }, (_, i) => i);   // nodes are 1..n
  const size = new Array(edges.length + 1).fill(1);
  const find = x => {
    while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }   // path halving
    return x;
  };
  for (const [a, b] of edges) {
    let ra = find(a), rb = find(b);
    if (ra === rb) return [a, b];        // already connected: closes the cycle
    if (size[ra] < size[rb]) [ra, rb] = [rb, ra];
    parent[rb] = ra;
    size[ra] += size[rb];
  }
  return [];
}

fn solve(edges: &[[i64; 2]]) -> Vec<i64> {
    let n = edges.len();
    let mut parent: Vec<usize> = (0..=n).collect();       // nodes are 1..n
    let mut size = vec![1usize; n + 1];
    fn find(parent: &mut Vec<usize>, mut x: usize) -> usize {
        while parent[x] != x {
            parent[x] = parent[parent[x]];                  // path halving
            x = parent[x];
        }
        x
    }
    for e in edges {
        let mut ra = find(&mut parent, e[0] as usize);
        let mut rb = find(&mut parent, e[1] as usize);
        if ra == rb {
            return vec![e[0], e[1]];                        // closes the cycle
        }
        if size[ra] < size[rb] {
            std::mem::swap(&mut ra, &mut rb);
        }
        parent[rb] = ra;
        size[ra] += size[rb];
    }
    Vec::new()
}

import qualified Data.Map.Strict as M

solve :: [[Int]] -> [Int]
solve = go M.empty
  where
    -- parent map: a node absent from the map is its own root (no compression: n <= 1000 keeps it fast)
    root p x = case M.lookup x p of
      Just y | y /= x -> root p y
      _ -> x
    go _ [] = []
    go p ([a, b] : rest)
      | ra == rb = [a, b]                       -- already connected: closes the cycle
      | otherwise = go (M.insert ra rb p) rest
      where
        ra = root p a
        rb = root p b

The same code is the reference solution to The connection that closes a loop, where it is compiled and run against the tests in all six languages.

TimeO(m · α(n))

SpaceO(n)

Effectively linear. Without the two refinements a chain can form and each find becomes O(n).

Use union-find when edges arrive over time, when you need to count groups as they merge, or inside Kruskal's algorithm. Use a traversal when the graph is fixed and you need paths or distances, which union-find does not provide, or when edges can be deleted, which it cannot handle.