Disjoint Set Union (Union-Find)

July 2026 · 35 min read

Introduction

Imagine a social network where people form friend groups. Two people are in the same group if they are connected by any chain of friendships. When two people from different groups become friends, their entire groups merge. At any point, we want to quickly answer: “Are Alice and Bob in the same friend group?”

This is exactly the problem that Disjoint Set Union (DSU), also known as Union-Find, solves. It maintains a collection of disjoint sets (non-overlapping groups) and supports two fundamental operations:

• Find(x) — determine which set element x belongs to (by returning a “representative” or root of that set).
• Union(x, y) — merge the sets containing x and y into a single set.

In this post we will build DSU from scratch, layer on each optimization with visual step-by-step examples, build an interactive animation, cover advanced variants (rollback, weighted, small-to-large), write production-quality C++ code, and explore competitive programming applications.

Naive Implementation

The simplest way to track which set each element belongs to is an array id[] where id[x] stores the set representative (label) of element x. Initially, each element is its own representative: id[x] = x.

Find(x): Simply return id[x]. This is O(1).

Union(x, y): To merge the sets of x and y, scan the entire array and change every occurrence of id[y] to id[x]. This is O(n).

After Union(1, 3) and Union(3, 5):

Elements 1, 3, and 5 now share representative 1. Find is O(1) but Union is O(n), giving O(n·m) for m operations total. We need something better.

Tree-Based Representation

Instead of a flat array, represent each set as a rooted tree. Use a parent[] array where parent[x] points to x’s parent, and the root points to itself (parent[root] = root). The root serves as the set representative.

Find now walks up the tree from x to its root. Union simply makes one root point to the other. Both operations take O(tree height) time.

But without care, the tree can degenerate into a chain (like a linked list), making both Find and Union O(n) in the worst case. For example, if we union 0→1, then 1→2, then 2→3, etc., we get a single chain of length n.

Two key optimizations fix this: path compression and union by rank/size.

Path Compression

Path compression is a strikingly simple optimization: during Find(x), after walking all the way up to the root, we make every node along the path point directly to the root. This flattens the tree so that future Find operations on those nodes are nearly instant.

Let’s walk through a concrete example. Consider a tree with 7 nodes where node 6 is a deep leaf:

Path compression alone (without union by rank) gives amortized O(log n) per operation. But when combined with union by rank, we get something even better.

Union by Rank / Size

The second optimization controls how we merge two trees. The idea: always attach the smaller (or shorter) tree under the root of the larger tree. This prevents the tree from growing tall.

There are two variants:

Let’s trace a sequence of union operations with union by rank on 8 elements:

Combined Optimizations & Complexity

When we use both path compression and union by rank/size, the amortized time per operation becomes O(α(n)), where α is the inverse Ackermann function.

The Inverse Ackermann Function

The Ackermann function A(m, n) grows extraordinarily fast — faster than any primitive recursive function. Its inverse α(n) grows correspondingly slowly:

For any conceivable input size in the universe (< 2⁶⁵⁵³⁶), α(n) ≤ 4. This means DSU with both optimizations is effectively O(1) per operation for all practical purposes.

Why It’s Nearly O(1) — Proof Sketch

The formal proof by Tarjan (1975) uses a potential function argument. Here’s the high-level intuition:

1. Union by rank guarantees that a tree with rank r has at least 2^r nodes. This bounds the number of distinct ranks to O(log n).
2. Path compression flattens trees aggressively. After a Find, every node on the path becomes a direct child of the root. Subsequent Finds on those nodes are O(1).
3. The key insight: partition the ranks into blocks using the iterated logarithm (log*). Path compression ensures that any node eventually “jumps” to a parent in a higher rank block. The total number of such jumps across all operations is bounded by O(n · α(n)).
4. Distributing this cost across m operations gives O(α(n)) amortized per operation.

Interactive Animation

Step through a sequence of Union and Find operations on 8 elements. Watch the forest of trees evolve, see path compression flatten the tree on Find, and observe union by rank maintaining balance. The parent and rank arrays update in real time.

Rollback DSU (Persistent)

In standard DSU with path compression, operations are irreversible — once you compress a path, you can’t undo it. But some problems (especially offline divide-and-conquer on queries) require us to undo union operations.

Rollback DSU uses union by rank without path compression and maintains a stack of changes. Each union records what was changed, and a rollback simply restores those values.

How It Works

1. Union: Before modifying parent[py] and rank[px], push the old values onto a history stack.
2. Rollback: Pop the stack and restore the saved values. This undoes the most recent union.
3. Checkpoint: Save the current stack size. Later, roll back all unions performed after the checkpoint by restoring entries until the stack returns to that size.

When to Use Rollback DSU

• Offline divide-and-conquer on edges: Process queries on segments of time using D&C on a segment tree of queries. Add edges when entering a segment, roll back when leaving.
• Dynamic connectivity (offline): Each edge has a time interval [l, r) when it exists. Use a segment tree on time and rollback DSU to answer connectivity queries.
• Link-Cut problems: When you need both union and split, rollback DSU provides a clean offline solution.

DSU with Additional Information

Standard DSU answers “are x and y in the same set?” But we can augment the DSU to maintain extra information along the edges, enabling it to answer more nuanced queries.

Weighted DSU (Distance to Root)

Store a weight[x] value representing the “distance” (or potential difference) from node x to its parent. This lets us answer queries like: “What is the relative difference between x and y?”

During path compression, accumulate the weights along the path:

Application: Given constraints like “A − B = 5” and “B − C = 3”, we can infer “A − C = 8” and detect contradictions.

Parity DSU (Bipartiteness Checking)

A special case of weighted DSU where weights are in ℤ₂ (0 or 1). This is perfect for checking if a graph is bipartite as edges are added online.

Each edge (u, v) means “u and v are in different partitions,” which translates to weight 1 (parity difference). If we ever find u and v in the same set with even parity, adding an edge between them would create an odd cycle — not bipartite!

Tracking Set Sizes

The most common augmentation: store the size of each component at the root. Increment the root’s size during union. This lets you answer queries like “how many elements are in the same set as x?” in O(α(n)).

Small-to-Large Merging

Small-to-large merging (also called the weighted union heuristic or merge by size) is a general technique that extends beyond DSU: when merging two sets, always iterate over the smaller set and insert its elements into the larger set.

Why O(n log n) Total

Every time an element is moved, the set it joins is at least twice as large as the set it came from. Therefore, each element can be moved at most log₂(n) times before it’s in a set of size n. Total work across all merges: O(n log n).

Applications Beyond DSU

• Merging sets with auxiliary data: Each DSU node owns a std::set or std::map. When unioning, iterate the smaller container and insert into the larger one. Total: O(n log² n).
• Euler Tour Trees: Merging subtree information using the small-to-large principle.
• Heavy-Light Decomposition: HLD’s chain selection is conceptually similar — always extending the “heavier” child’s chain.
• DSU on tree (small to large on children sets): Process queries on a tree by merging children’s answer sets into the parent. Total O(n log n) with careful merging.

Example: maintain the set of distinct colors in each component.

// Small-to-large merging with std::set
vector<set<int>> colors(n);
// Initially, colors[i] = {color_of_node_i}

void merge(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (colors[x].size() < colors[y].size()) swap(x, y);
    // x is larger, y is smaller
    for (int c : colors[y]) colors[x].insert(c);
    colors[y].clear();
    parent[y] = x;
}
// Each element moves O(log n) times => total O(n log^2 n)

C++ Implementation

Basic DSU with Path Compression + Union by Rank

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent, rank_;

    DSU(int n) : parent(n), rank_(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // path compression
        return parent[x];
    }

    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (rank_[x] < rank_[y]) swap(x, y);
        parent[y] = x;
        if (rank_[x] == rank_[y]) rank_[x]++;
        return true;
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    int n = 8;
    DSU dsu(n);

    dsu.unite(0, 1);
    dsu.unite(2, 3);
    dsu.unite(0, 2);
    dsu.unite(4, 5);
    dsu.unite(6, 7);
    dsu.unite(4, 6);
    dsu.unite(0, 4);

    // All elements now in the same set
    for (int i = 0; i < n; i++)
        cout << "find(" << i << ") = " << dsu.find(i) << "\n";

    cout << "connected(1,7) = " << dsu.connected(1, 7) << "\n";  // 1
    cout << "connected(0,5) = " << dsu.connected(0, 5) << "\n";  // 1
    return 0;
}

DSU with Rollback

struct RollbackDSU {
    vector<int> parent, rank_;
    vector<pair<int*,int>> history;  // (pointer, old_value)

    RollbackDSU(int n) : parent(n), rank_(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

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

    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        if (rank_[x] < rank_[y]) swap(x, y);
        // Save state before modification
        history.push_back({&parent[y], parent[y]});
        history.push_back({&rank_[x], rank_[x]});
        parent[y] = x;
        if (rank_[x] == rank_[y]) rank_[x]++;
        return true;
    }

    int checkpoint() { return history.size(); }

    void rollback(int cp) {
        while ((int)history.size() > cp) {
            auto [ptr, val] = history.back();
            *ptr = val;
            history.pop_back();
        }
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

// Usage: offline divide-and-conquer
// int cp = dsu.checkpoint();
// dsu.unite(a, b);  // add edge
// ... process queries ...
// dsu.rollback(cp);  // undo all unions since checkpoint

Weighted DSU

struct WeightedDSU {
    vector<int> parent, rank_;
    vector<long long> weight;  // weight[x] = potential from x to parent[x]

    WeightedDSU(int n) : parent(n), rank_(n, 0), weight(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }

    // Returns {root, distance_from_x_to_root}
    pair<int, long long> find(int x) {
        if (parent[x] == x) return {x, 0};
        auto [root, w] = find(parent[x]);
        parent[x] = root;
        weight[x] += w;
        return {root, weight[x]};
    }

    // Add relation: potential[y] - potential[x] = w
    // Returns false if contradicts existing relations
    bool unite(int x, int y, long long w) {
        auto [rx, wx] = find(x);
        auto [ry, wy] = find(y);
        if (rx == ry) return (wy - wx) == w;  // check consistency
        if (rank_[rx] < rank_[ry]) {
            swap(rx, ry);
            swap(wx, wy);
            w = -w;
        }
        parent[ry] = rx;
        weight[ry] = wx - wy + w;
        if (rank_[rx] == rank_[ry]) rank_[rx]++;
        return true;
    }

    // Get potential[y] - potential[x], or nullopt if different sets
    optional<long long> diff(int x, int y) {
        auto [rx, wx] = find(x);
        auto [ry, wy] = find(y);
        if (rx != ry) return nullopt;
        return wy - wx;
    }
};

// Usage: "A is 5 more than B" => dsu.unite(B, A, 5)
// Query: "How much more is A than C?" => dsu.diff(C, A)

Applications in Competitive Programming

More Applications

• Connected components counting: After processing edges, the number of distinct roots equals the number of connected components.
• Cycle detection in undirected graphs: If find(u) == find(v) before unioning u and v, the edge (u, v) creates a cycle.
• Minimum spanning arborescence: Edmond’s algorithm uses DSU for contracting cycles.
• LCA in offline: Tarjan’s offline LCA algorithm processes queries using DFS + DSU.
• Physics simulation: Percolation problems model connectivity in grids using DSU.
• Image segmentation: Merge adjacent pixels with similar colors using union-find.

Practice Problems

Summary

Let’s recap the key takeaways:

1. Disjoint Set Union maintains a partition of elements into non-overlapping sets with near-constant-time Find and Union operations.
2. Path compression flattens trees during Find by pointing all nodes on the path directly to the root.
3. Union by rank/size keeps trees balanced by attaching the smaller tree under the larger one.
4. Combined, they achieve O(α(n)) amortized per operation — practically O(1) for any real-world input.
5. Rollback DSU sacrifices path compression for undo capability, essential for offline divide-and-conquer problems.
6. Weighted DSU stores edge weights to track relative differences between elements (useful for parity checking, potential functions).
7. Small-to-large merging is a general O(n log n) technique that underpins union by size and extends to merging auxiliary data structures.
8. DSU is the engine behind Kruskal’s MST, dynamic connectivity, cycle detection, and countless CP problems.