Disjoint Set Union (Union-Find) study guide

Oct 17, 2026 · @Muneeb

A disjoint set union (DSU, also called union-find) is a tool for keeping track of groups. It can quickly tell you whether two things are in the same group, and quickly merge two groups into one. Each step is almost instant (technically O(α(n)), which is effectively constant). This guide explains the idea in plain words, shows traced runs of real code, and ends with a practice list with no solutions.

What a DSU is

Think of friend groups. Every group has one captain. To check whether two people are in the same group, ask each one “who is your captain?” If the answers match, they are in the same group. To merge two groups, make one captain report to the other captain.

A DSU does exactly this with one array. parent[x] is the person that x reports to. A captain reports to themselves. If you keep following the parents, you always end at the captain. We call the captain the root.

Read the picture below from left to right. Eight people start alone. Four merges make pairs. Three more merges join everyone into one group. The whole structure is just the array [0, 0, 0, 0, 0, 4, 4, 4], plus a size[] array that keeps the trees short.

[embedded content: union-find forest · 8 elements, 7 merges]

The two operations and the Java class to memorise

find(x) walks up the parents until it reaches the captain (the root), and returns it. union(a, b) finds both captains and makes one report to the other. If both already have the same captain, they are already together, so nothing happens.

class DSU {
    int[] parent, size;
    int components;                       // number of sets right now

    DSU(int n) {
        parent = new int[n];
        size = new int[n];
        components = n;
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }

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

    boolean union(int a, int b) {         // union by size
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;       // already in the same set
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        size[ra] += size[rb];
        components--;
        return true;
    }

    boolean connected(int a, int b) { return find(a) == find(b); }
}

Every variant later in this guide is this same class with one extra array. union returns true if it merged two groups, and false if they were already together. That true or false answer is the trick behind cycle detection and Kruskal’s algorithm below. This class was compiled and checked against a simple search on 2,000 random graphs.

Why plain DSU is slow, and the two fixes

The plain version has a problem. If you call union(0, 1), union(1, 2), union(2, 3) and so on with no rules, you get one long chain. Then find(0) has to walk the whole chain. With 6 elements the array ends as [1, 2, 3, 4, 5, 5] and find(0) takes 5 steps. With a million elements it would take a million steps. Two small fixes solve this.

Fix 1: path compression. After find reaches the captain, it tells everyone it walked past: “your parent is now the captain directly.” Next time, those people reach the captain in one step. After one find(0), the chain [1, 2, 3, 4, 4] becomes [4, 4, 4, 4, 4].

[embedded content: path compression · chain of 5 before and after one find]

Fix 2: union by size. When merging, put the smaller group under the bigger group’s captain. A person only gets one level deeper when their group ends up inside one at least as big, so their group at least doubles. That means no one can be deeper than log2 n levels (about 20 levels for a million people).

[embedded content: union by size · two ways to merge a 3-node and a 1-node tree]

Together, the two fixes make every operation almost instant. The exact cost is O(α(n)) per operation on average, where α grows so slowly that it never goes above 4 for any realistic n (cp-algorithms). Either fix alone gives O(log n), which is also fast. The same page reports that choosing which tree goes under which by coin flip performs much worse than union by size.

Types of DSU

There are two different questions here: how the structure is made fast (implementation variants), and what extra it remembers to answer a problem (problem variants).

Implementation variants

Problem variants

A full run on eight elements

This table is the recorded state after each operation of the DSU class above. When two sets have equal size, the second root is hung under the first.

Step 5: roots 0 and 2 each hold two elements, so the tie hangs 2 under 0. Step 7: find(3) climbs 3, 2, 0 and find(7) climbs 7, 6, 4; path compression rewires 3 and 7 on the way, then the two size-4 trees tie and 4 goes under 0. Step 8: 0 and 7 already share root 0, so union returns false and compression points 7 straight at 0.

After step 8 every node is within two hops of the root, which is what union by size guarantees (height at most log2 8 = 3).

When to reach for a DSU, and when not to

Reach for a DSU when the problem only ever merges groups and asks about group membership.

Avoid it when you need an actual path or a shortest distance (use BFS or Dijkstra), when edges are removed between online queries, or when edges are directed and the direction matters. A DSU only models undirected connectivity.

Pattern 1: connectivity, component counts and cycles

Treat every edge as union(u, v). Afterwards components is the number of connected components and connected(u, v) says whether a path exists. union returns false exactly when u and v were already connected, so that edge closes a cycle.

Run on n = 4 with edges 0-1, 1-2, 2-3, 3-1:

Two facts follow from the mechanics. Every successful union lowers the component count by exactly one. A graph on n vertices is a tree exactly when every union succeeds and there are n-1 edges.

Pattern 2: Kruskal’s minimum spanning tree

Sort the edges by weight and take an edge only when union succeeds. The DSU makes the cycle check near-constant, so the sort dominates and the total is O(m log m). cp-algorithms notes the DSU is what brings Kruskal from O(m log n + n²) down to O(m log n).

Run on 5 vertices with edges (0-1, w4), (0-2, w3), (1-2, w1), (1-3, w2), (2-3, w4), (3-4, w2). Ties keep their input order.

[embedded content: Kruskal on a 5-vertex graph · 4 edges taken, 2 skipped]

Arrays.sort(edges, (x, y) -> Integer.compare(x[2], y[2]));   // not x[2] - y[2], which can overflow
DSU d = new DSU(n);
int total = 0;
for (int[] e : edges)
    if (d.union(e[0], e[1])) total += e[2];

A spanning tree needs n-1 edges, so you can stop as soon as d.components == 1.

Bottleneck paths. If you add edges in increasing weight and stop the moment s and t become connected, the weight of the last edge added is the smallest possible value of the largest edge on any s-to-t path. That is the quantity behind “minimum effort” and “swim in rising water” style problems.

Pattern 3: nodes that are not 0 to n-1

Real problems rarely hand you integer ids. These are the standard ways to fit them.

• Grid cells. Map (r, c) to r * cols + c. Union only with the right and down neighbours; the other two directions are covered when those neighbours take their turn.
• A special “outside”. Add one dummy node (index n) and union every boundary element with it. Anything connected to the dummy touches the boundary.
• Strings, emails, names. Give each distinct key an int id with a HashMap<String, Integer>, or run the DSU on a HashMap<String, String> parent map.
• Connect through a shared node, not pairwise. If items share a property (a row, a column, a prime factor), union each item with a node that stands for the property instead of comparing every pair of items. That turns O(n²) pair checks into one union per item per property.
• Aggregates at the root. Keep size, min, max or sum in an array indexed by root, and merge it inside union.

int id(int r, int c) { return r * cols + c; }

for (int r = 0; r < rows; r++)
    for (int c = 0; c < cols; c++) {
        // the condition depends on the problem; here: equal values
        if (r + 1 < rows && grid[r + 1][c] == grid[r][c]) d.union(id(r, c), id(r + 1, c));
        if (c + 1 < cols && grid[r][c + 1] == grid[r][c]) d.union(id(r, c), id(r, c + 1));
    }

An aggregate rides along with the union. Here, the smallest label in each set:

int[] min;                                   // min[root] = smallest label in that set

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];
    min[ra] = Math.min(min[ra], min[rb]);    // merge the aggregate into the new root
    return true;
}

The root chosen by union by size is arbitrary. When a problem wants a specific leader (the smallest, say), keep it in an aggregate like min[] instead of reading it off parent. cp-algorithms makes the same point.

Variant: parity DSU (bipartite check, online)

Store each node’s colour relative to its parent: parity[x] = colour(x) xor colour(parent[x]). find accumulates parity along the path, so path compression stays valid. For an edge a-b with the same root, equal colours mean an odd cycle and the graph is not bipartite. With different roots, hang one root under the other with parity[rb] = parity[a] ^ parity[b] ^ 1, so a and b land on opposite sides. cp-algorithms derives the same formula.

[embedded content: parity colouring · a 4-cycle and a triangle]

class ParityDSU {
    int[] parent, size, parity;

    ParityDSU(int n) {
        parent = new int[n]; size = new int[n]; parity = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }

    int find(int x) {
        if (parent[x] == x) return x;
        int p = parent[x];
        int r = find(p);
        parity[x] ^= parity[p];          // parity[p] is now relative to the root
        parent[x] = r;
        return r;
    }

    boolean addEdge(int a, int b) {      // false if the edge creates an odd cycle
        int ra = find(a), rb = find(b);
        if (ra == rb) return parity[a] != parity[b];
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        parity[rb] = parity[a] ^ parity[b] ^ 1;
        size[ra] += size[rb];
        return true;
    }
}

Recorded runs. A 4-cycle is bipartite:

A triangle is not:

This class matched a BFS two-colouring on 3,000 random graphs. For a static graph a BFS colouring is simpler; the DSU wins when edges arrive online or when the constraints say “these two must differ”.

Variant: weighted DSU (relative values)

Store the offset to the parent: pot[x] = val[x] - val[parent[x]]. find adds up offsets along the path while compressing, so after find(x) the entry pot[x] is x’s value relative to its root. A fact “val[a] - val[b] = d” either merges two roots, setting pot[ra] = d - pot[a] + pot[b], or, when the roots already match, is checked against pot[a] - pot[b]. For ratios the same code works with multiplication in place of addition and division in place of subtraction.

class WeightedDSU {
    int[] parent; long[] pot;                // pot[x] = val[x] - val[parent[x]]

    WeightedDSU(int n) {
        parent = new int[n]; pot = new long[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    int find(int x) {
        if (parent[x] == x) return x;
        int p = parent[x];
        int r = find(p);
        pot[x] += pot[p];                    // pot[p] is now relative to the root
        parent[x] = r;
        return r;
    }

    boolean addFact(int a, int b, long d) {  // val[a] - val[b] = d; false on a contradiction
        int ra = find(a), rb = find(b);
        if (ra == rb) return pot[a] - pot[b] == d;
        parent[ra] = rb;
        pot[ra] = d - pot[a] + pot[b];
        return true;
    }

    Long diff(int a, int b) {                // val[a] - val[b], or null if unknown
        if (find(a) != find(b)) return null;
        return pot[a] - pot[b];
    }
}

This version links without a size rule so the algebra stays visible. To add union by size, hang the other root instead and negate the offset: pot[rb] = -(d - pot[a] + pot[b]).

Recorded run with a = 0, b = 1, c = 2:

In step 3, find(0) climbs 0, 1, 2 and compresses, so pot[0] becomes 3 + 2 = 5.

Variant: offline processing and reverse time

A DSU only merges and never splits, and two tricks make that enough.

Sort by a limit. For queries like “is there a path using only edges lighter than L?”, sort the edges by weight and the queries by L. Sweep through the queries, and before answering each one, union every edge below its limit. Keep each query’s original index so the answers can be put back in order. The same sweep answers “earliest time when X holds”: sort edges by time and stop when the condition becomes true.

Reverse time for deletions. If edges disappear over time, run the clock backwards. Start from the graph after all deletions, then add the edges back in reverse order of deletion. The state after t deletions is the state after adding back k - t edges, where k is the total number of deletions.

Example: a 5-cycle with edges e0 = 0-1, e1 = 1-2, e2 = 2-3, e3 = 3-4, e4 = 4-0. Delete e1, then e3, then e0, and count components after each deletion.

Read forwards, the cycle stays connected after e1 goes, splits in two after e3, and in three after e0. The recorded run printed [1, 1, 2, 3] for 0 to 3 deletions and matched a brute-force rebuild after every deletion.

Variant: rollback DSU

To undo a union you cannot have compressed any paths, so a rollback DSU uses union by size only. find costs O(log n), and every union call pushes a record on a stack. Undoing pops the record, makes the child root its own root again and subtracts its size from the parent. It supports offline dynamic connectivity (edges that exist only during a time interval). It is rare on LeetCode and common in contests.

class RollbackDSU {
    int[] parent, size;
    Deque<int[]> history = new ArrayDeque<>();

    RollbackDSU(int n) {
        parent = new int[n]; size = new int[n];
        for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }
    }

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

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) { history.push(new int[]{-1, -1}); return false; }  // one record per call
        if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
        parent[rb] = ra;
        size[ra] += size[rb];
        history.push(new int[]{rb, ra});
        return true;
    }

    void rollback() {                        // undo the latest union() call
        int[] h = history.pop();
        if (h[0] == -1) return;
        parent[h[0]] = h[0];
        size[h[1]] -= size[h[0]];
    }
}

Recorded run on n = 5:

size is only meaningful at roots, so stale values at non-roots are harmless.

Pitfalls in Java

• Recursion depth. A recursive find is safe with union by size (depth at most log2 n). With compression alone, a chain of 100,000 nodes can throw StackOverflowError. The iterative form below uses path halving and needs no recursion.
• Compare roots, never parents. parent[a] == parent[b] is wrong unless both are already compressed. Use find(a) == find(b).
• size[] is only valid at roots. Call find first, then read size[root].
• Group by find(i), not parent[i]. After unions, a non-root’s parent can be two or more hops from its root.
• 1-indexed inputs. Allocate n + 1 and ignore index 0, or subtract 1 on the way in.
• Directed edges. A DSU treats every edge as undirected. Directed problems need extra reasoning, such as in-degrees.
• A fresh DSU per test. A judge may reuse one Solution object across test cases. Create the DSU inside the method instead of keeping it in a field from an earlier call.
• Offline queries. Keep each query’s original index when you sort, or the answers come back in the wrong order.
• Comparators. Sort with Integer.compare(x, y); x - y can overflow.

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

Complexity cheat sheet

Building any of these is O(n). Kruskal costs O(m log m) for the sort plus m unions at O(α(n)) each.

Practice problems by pattern (no solutions)

Attempt each problem after rereading the section named in the Pattern column; that column names an idea to revisit and nothing more. Tiers are my own order of difficulty, not LeetCode’s labels, and the pattern tags are my own classification. “P” marks a problem that, as far as I know, needs LeetCode Premium. Numbers and titles come from the walkccc Union-Find list; search LeetCode by number.

Tier 1: plain connectivity, counts and cycles

Tier 2: grids, strings and other kinds of nodes

Tier 3: spanning trees and bottleneck paths

Tier 4: offline queries and reverse time

Tier 5: parity, weights and harder modelling

Beyond LeetCode. The cp-algorithms DSU article lists Codeforces 25D (Roads not only in Berland), Timus 1003 (Parity) and SPOJ CHAIN (Strange Food Chain); the last two are good parity and relation exercises.

Suggested order. Finish Tier 1 first, then Tier 2. After that, take one problem from each remaining tier before going deep on any. Return to a solved problem and redo it with a different variant from this guide; that is where the patterns stick.

Sources

• Disjoint Set Union, cp-algorithms: definition, optimisations, complexity, parity, applications.
• Union Find templates, lctemplates: size and rank templates, weighted DSU.
• Union-Find problem list, walkccc: problem numbers and titles.
• 10 Interesting Problems of DSU, LeetCode Discuss: problem patterns.

All code and traces were compiled and run on Java 21 and cross-checked against BFS on random graphs. The path halving snippet and the problem pattern tags come from general knowledge and my own classification, not from the pages above.