Lesson 6 · Non-linear structures

Disjoint Sets and Union-Find

A Disjoint Set (or Union-Find) structure tracks a set of elements partitioned into non-overlapping subgroups. It is hyper-optimized to answer one question: 'Are these two items in the same group?'

The Problem It Solves

A disjoint set, usually called union-find, maintains a collection of elements partitioned into non-overlapping groups. Every element belongs to exactly one group, and the structure answers one question and performs one change: are these two elements in the same group, and merge these two groups into one.

Notice how narrow that is. There is no way to list a group's members, no way to iterate a group, and — critically — no way to split one. The structure is built for merging only. In exchange for giving all that up, it performs both of its operations in essentially constant time, which no general graph structure can match.

The situation it fits is dynamic connectivity. Imagine a network where cables are added one at a time and you must answer, after each addition, whether two machines can now reach each other. Recomputing connectivity from scratch with BFS or DFS costs O(V + E) per query. Union-find answers it in near-constant time by maintaining the grouping incrementally.

Two operations define the interface. find(x) returns a representative — a canonical element identifying x's group, chosen arbitrarily but consistently. union(x, y) merges the two groups containing x and y. Testing whether x and y are connected is then simply find(x) == find(y): they share a group precisely when they share a representative.

Maintains a partition: every element in exactly one group
find returns the group's representative; union merges two groups
Connected means find(x) == find(y)
Supports merging only — groups can never be split apart

Sets as Trees

Each set is represented as a tree, stored not with node objects but with a single array: parent[i] holds the index of i's parent. An element that is its own parent — parent[i] == i — is a root, and the root is the set's representative.

Initially every element is its own single-node tree, so parent[i] = i for all i and there are n separate sets. This initialisation is O(n) and is the only part of the structure that touches every element.

find(x) walks up the parent chain until it reaches an element that is its own parent, and returns it. Its cost is therefore the height of the tree — which is exactly why the two optimisations below both exist to attack height.

union(x, y) finds both roots and, if they differ, makes one root point at the other. That single write merges two entire trees, however large, because everything beneath a root moves with it implicitly. If the roots are already equal the elements were already grouped and nothing happens.

The naive version has a serious flaw. Attaching arbitrarily can build a chain: union(1,2), union(2,3), union(3,4) and so on produces a tree of height n − 1, degenerating find to O(n). Both optimisations below exist to prevent exactly this.

One parent array; a root is an element whose parent is itself
find walks to the root, costing the height of the tree
union points one root at the other — one write merges everything
Naive attachment can build a chain and make find O(n)

Union by Rank and Path Compression

Union by rank fixes which root becomes the parent instead of choosing arbitrarily. Each root carries a rank, an upper bound on its tree's height, and the union always attaches the shorter tree under the taller one. Hanging a short tree off a tall one does not increase the height at all; only merging two trees of equal rank does, and then by exactly one, so the rank is incremented.

Because height only grows when two equal-rank trees merge, and a tree of rank r must contain at least 2^r elements, the height is bounded by log n. That alone takes find from O(n) to O(log n).

A common variant, union by size, attaches the tree with fewer elements under the larger one. It gives the same logarithmic bound and needs a count rather than a rank; the counts are also directly useful when a problem asks for the size of a component.

Path compression attacks the problem from the other direction. Since find already walks from x up to the root, it may as well record what it learned: on the way back, point every node on that path directly at the root. The next find on any of them terminates in one step.

This is a self-improving structure — each query makes subsequent queries cheaper, and repeated access to the same region flattens it almost completely. Two lines of recursion express it: find the root recursively, assign it to parent[x], and return it. An iterative form doing two passes avoids deep recursion on large inputs.

Together the two are stronger than either alone. Union by rank prevents tall trees from forming; path compression flattens whatever tall trees do form. Using only one gives O(log n); using both gives the near-constant bound below.

What each optimisation buys, per operation, amortised
Optimisations	find / union	Note
Neither	O(n)	A chain of unions degenerates the tree
Union by rank only	O(log n)	Height bounded by log n
Path compression only	O(log n) amortised	Flattens on access
Both	O(α(n))	α(n) ≤ 4 for any n that fits in memory

Union by rank attaches the shorter tree under the taller
Height grows only when equal ranks merge, bounding it at log n
Path compression repoints every node on the path to the root
Both together are strictly better than either alone

Key reference

Terms, operations, and practical uses

Core vocabulary

Disjoint SetsA collection of sets where no element belongs to more than one set.
Representative (Root)The unique element used to identify a specific set. If two elements have the same root, they are in the same set.
Connected ComponentA maximal set of vertices in a graph that are all reachable from one another.

Operations

FindAn operation that returns the root representative of the set containing a given element.
UnionAn operation that merges two sets by making the root of one set point to the root of the other.
InitializationStarting state where every element is in its own set (i.e., its parent is itself).

Optimizations

Path CompressionAn optimization in Find that makes every visited node point directly to the root, flattening the tree.
Union by RankAn optimization in Union that always attaches the shorter tree under the root of the taller tree to keep the tree shallow.
Inverse Ackermann α(N)The resulting amortized time complexity, which is so slow-growing it is effectively O(1) for any practical input size.

Implementation

Union by rank and Find with path compression

parent = list(range(6))   # every element is its own root
rank = [0] * 6            # tree height, used to keep unions shallow

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])   # path compression
    return parent[x]

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False                  # already together: this edge is a cycle
    if rank[ra] < rank[rb]:
        ra, rb = rb, ra               # attach the shorter tree
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1
    return True

union(0, 1)
union(2, 3)
union(1, 3)

groups = {}
for i in range(6):
    groups.setdefault(find(i), []).append(i)
shown = ' plus ' + ' and '.join('{ ' + ', '.join(map(str, g)) + ' }'
                                for g in list(groups.values())[1:
                                    ])
print('Root of 0 is', find(0), '— one set { ' + ', '.join(map(str, list(groups.values())[0])) + ' },' + shown)

#include <iostream>
#include <map>
#include <numeric>
#include <vector>
using namespace std;
vector<int> parent(6);
vector<int> rnk(6, 0); // tree height, used to keep unions shallow
int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]); // path compression
    return parent[x];
}
bool unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false; // already together: a cycle
    if (rnk[ra] < rnk[rb]) swap(ra, rb); // attach the shorter tree
    parent[rb] = ra;
    if (rnk[ra] == rnk[rb]) rnk[ra]++;
    return true;
}
int main() {
    iota(parent.begin(), parent.end(), 0); // every element is its own root
    unite(0, 1);
    unite(2, 3);
    unite(1, 3);
    map<int, vector<int>> groups;
    for (int i = 0; i < 6; i++) groups[find(i)].push_back(i);
    cout << "Root of 0 is " << find(0);
    bool first = true;
    for (auto& g : groups) {
        cout << (first ? " — one set { " : " { ");
        for (size_t i = 0; i < g.second.size(); i++) {
            if (i) cout << ", ";
            cout << g.second[i];
        }
        cout << " }";
        if(first) {
            cout << ", plus";
            first = false;
        } else if (g.first != groups.rbegin()->first) cout << " and";
    }
    cout << '\n';
}

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
class Main {
    static int[] parent = new int[6];
    static int[] rank = new int[6]; // tree height, used to keep unions shallow
    static int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
        return parent[x];
    }
    static boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false; // already together: a cycle
        if(rank[ra] < rank[rb]) {
            int t = ra;
            ra = rb;
            rb = t;
        }
        parent[rb] = ra;
        if (rank[ra] == rank[rb]) rank[ra]++;
        return true;
    }
    public static void main(String[] args) {
        for (int i = 0; i < 6; i++) parent[i] = i; // every element is its own root
        union(0, 1);
        union(2, 3);
        union(1, 3);
        Map<Integer, List<Integer>> groups = new LinkedHashMap<>();
        for (int i = 0; i < 6; i++) groups.computeIfAbsent(find(i), k -> new ArrayList<>()).add(i);
        StringBuilder sb = new StringBuilder("Root of 0 is " + find(0));
        boolean first = true;
        int seen = 0;
        for (List<Integer> g : groups.values()) {
            seen++;
            sb.append(first ? " — one set { " : " { ");
            for (int i = 0; i < g.size(); i++) {
                if (i > 0) sb.append(", ");
                sb.append(g.get(i));
            }
            sb.append(" }");
            if(first) {
                sb.append(", plus");
                first = false;
            } else if (seen < groups.size()) sb.append(" and");
        }
        System.out.println(sb);
    }
}

Watch it run

Step through it

Running on 6 elements. union(0,1), union(2,3), union(1,3), find(0)

Output

Read all 11 Steps

Six singleton sets Every element starts as its own root, so parent[x] = x and every rank is 0. There are six separate sets and no edges yet.
union(0, 1) — find both roots find(0) returns 0 and find(1) returns 1. The roots differ, so these are genuinely separate sets and the merge goes ahead.
union(0, 1) — equal rank, pick a root Both trees have rank 0, so either can win. We attach 0 under 1 and raise rank[1] to 1. Ties are the only time a rank increases.
union(2, 3) — find both roots The same check on the other pair: find(2) is 2, find(3) is 3. Different roots again, so this merge is allowed.
union(2, 3) — merge Rank 0 against rank 0 once more. Attach 2 under 3 and set rank[3] to 1. Now two two-element sets exist side by side.
union(1, 3) — find both roots find(1) is 1 and find(3) is 3. Two different roots, each of rank 1 — this is where union by rank earns its name.
union(1, 3) — attach root to root Equal rank, so 3 is attached under 1 and rank[1] becomes 2. Note we link the two roots, never a leaf — that is what keeps the tree shallow.
find(0) — step one Now trace a lookup. parent[0] is 1, which is not 0 itself, so 0 is not a root and the walk upward continues.
find(0) — reach the root parent[1] is 1. An element that is its own parent is the root, so the answer is 1. This walk took two hops.
Path compression on the way back As the recursion unwinds, every element visited is repointed straight at the root. Here parent[0] is already 1, so the shape does not change — but the rewrite is what keeps later lookups short.
Why it stays fast Had we called find(2), the walk 2 → 3 → 1 would rewrite parent[2] to 1, flattening that branch permanently. Rank keeps trees short and compression keeps them short; together they give near-constant amortised time.

Where It Is Used, and What Goes Wrong

Kruskal's algorithm for minimum spanning trees is the classic application. Edges are considered in increasing weight order, and each is accepted only if its endpoints are in different components — precisely a find comparison. Union-find is what makes the cycle check cheap enough for the algorithm to be practical.

Connected components in an undirected graph fall out immediately: union every edge, then count distinct roots. Cycle detection in an undirected graph is the same loop — encountering an edge whose endpoints already share a root means that edge closes a cycle. Grid problems such as counting islands or flood-filling regions are the same idea with implicit edges between adjacent cells.

Now the mistakes, which are consistent across implementations.

Comparing elements instead of roots. Testing x == y rather than find(x) == find(y) checks whether they are the same element, not whether they are grouped. Every connectivity test must go through find.

Unioning without finding first. Writing parent[x] = y instead of parent[find(x)] = find(y) reparents a single node rather than merging two sets, silently corrupting the partition.

Maintaining rank on non-roots. Rank is only meaningful for roots. Updating it elsewhere produces wrong balancing decisions that are hard to trace, since the structure still returns correct answers, only slowly.

Expecting deletion to work. Splitting a set is not supported and cannot be bolted on — path compression has already destroyed the information about how the tree was assembled. A problem requiring removals usually needs to be reversed: process the operations backwards so that deletions become unions.

Kruskal's MST, connected components, and undirected cycle detection
Always compare find(x) == find(y), never the raw elements
Union roots, not elements: parent[find(x)] = find(y)
No deletion — reverse the operation order to turn removals into unions