---
title: "Disjoint Set Union (Union–Find)"
summary: Two heuristics, one inverse-Ackermann bound, and the offline tricks that make it a problem-solving tool rather than a data structure.
difficulty: core
tags: [DSU, connectivity, Kruskal]
time: alpha(n) amortised
space: n
prereq: [foundations/connectivity]
see: [advanced-tree/mst, flow/cuts, directed/functional]
demo: dsu
---

:::definition label="The problem"
Maintain a partition of $\{0, \dots, n-1\}$ under two operations: `unite(a, b)` (merge the two classes) and `find(a)` (return a representative of $a$'s class). Nothing else is supported — that limitation is why it is $O(\alpha(n))$ instead of $O(\log n)$.
:::

```cpp dsu.cpp
struct DSU {
    vector<int> par, sz;
    DSU(int n) : par(n), sz(n, 1) { iota(par.begin(), par.end(), 0); }
    int find(int v) { while (v != par[v]) v = par[v] = par[par[v]]; return v; }  // path halving
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;                  // already together: the useful return value
        if (sz[a] < sz[b]) swap(a, b);
        par[b] = a; sz[a] += sz[b];
        return true;
    }
};
```

:::theorem title="Union by size alone: O(log n)"
After any sequence of unions, the depth of every vertex is at most $\log_2 n$.
:::

:::proof
A vertex's depth increases only when its root becomes a child of another root, and by the size rule that can only happen when the other tree is at least as large — so the subtree containing $v$ at least doubles each time $v$ goes one level deeper. Starting at size 1, at most $\log_2 n$ doublings fit inside $n$. ∎
:::

:::theorem title="With path compression: O(α(n)) amortised"
Union by size (or rank) plus path compression gives $O(\alpha(n))$ amortised per operation, where $\alpha$ is the inverse Ackermann function — at most 4 for $n$ up to $2^{65536}$.
:::

The proof (Tarjan; and the simpler $O((m+n)\log^* n)$ version) charges the cost of each `find` walk to "how many times did this vertex's parent change" and uses the doubling argument above to bound it by $\log^* n$, then a two-level partition of ranks improves $\log^*$ to $\alpha$. In practice the two heuristics differ like this: **without** compression, adversarial unions build $\Theta(\log n)$ chains; **without** union by size, compression alone is $O((m+n)\log n)$ amortised and can degrade badly on "union(0,1), union(1,2), union(2,3), …" with interleaved finds. Use both; they are one line each.

:::props title="Path halving vs full compression"
`par[v] = par[par[v]]` (halving, as above) is iterative, allocation-free and within a few percent of full two-pass compression — it is what you should type in a contest. Full compression recursively re-points every visited node; it wins when finds are extremely repeated, and it is the version to *prove* things about.
:::

## Extensions that are each two lines
:::example title="Rollback DSU (no path compression)"
For divide-and-conquer over time ("edge active on interval $[l, r]$") you need undo: record `(child, parent_size)` on a stack and revert. Depth is still $O(\log n)$ from union-by-size only, so each operation is $O(\log n)$ and queries are $O(\log^2 n)$ with segment-tree-over-time. Total $O(m \log m \log n)$, and it is the standard answer to "offline dynamic connectivity".
:::

```cpp dsu-rollback.cpp
struct RollbackDSU {
    vector<int> par, sz; vector<tuple<int,int,int>> hist;
    int find(int v) { while (par[v] != v) v = par[v]; return v; }        // no compression!
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) { hist.emplace_back(-1, -1, -1); return false; }
        if (sz[a] < sz[b]) swap(a, b);
        hist.emplace_back(b, a, sz[a]);
        par[b] = a; sz[a] += sz[b];
        return true;
    }
    void rollback() {   // undo one recorded step
        auto [b, a, sza] = hist.back(); hist.pop_back();
        if (b == -1) return;
        par[b] = b; sz[a] = sza;
    }
};
```

:::props title="Extra payloads"
- **size / sum / max / count** per class: keep an array indexed by the *root* and merge on `unite` — the pattern behind "largest connected component", "is this class all the same colour", bipartite-with-parity,
- **parity DSU** (weighted DSU with $d[x] \in \{0,1\}$ from parent): the 10-line solution to "constraints of the form $x \oplus y = c$" (@matching/applications, @special/twosat for the harder version),
- **DSU on successor lists**: `nxt[i]` skipping already-used positions — the "colour the first uncoloured position in $[l,r]$" trick, $O(n \alpha(n))$ for $m$ paint operations,
- **Kruskal**: sorting edges and uniting is literally running a sequence of graph *contractions* (@proofs/contracting, @advanced-tree/mst).
:::

:::demo id="dsu" caption="Free mode: click any two vertices to union them. Toggle path compression off, then union 0–1, 1–2, 2–3 … and watch `max depth` grow while the finds get slower."
:::

:::problems
- [[CSES 1666]] Building Roads | https://cses.fi/problemset/task/1666 | easy | components
- [[CF 25D]] Roads not only in Berland | https://codeforces.com/problemset/problem/25/D | easy | bridges via DSU
- [[CSES 1670]] Swap Game | https://cses.fi/problemset/task/1670 | core | state graph, contrast (BFS not DSU)
:::