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?'

What is a Disjoint Set?

Imagine a social network where people form distinct friend groups. A Disjoint Set keeps track of these groups. Every group has a single 'representative' or 'root' member.

If two people have the exact same representative, they belong to the same connected group.

Maintains a collection of non-overlapping sets
Every set has one unique representative (root)
Usually implemented using a simple flat array

Why it is useful

While you could use BFS or DFS on a Graph to find connected components, Union-Find is much faster and simpler when edges are being added dynamically one by one.

It is the core data structure used in Kruskal's Algorithm (to find Minimum Spanning Trees) and for quickly detecting cycles in undirected graphs.

Extremely fast dynamic connectivity checks
Cycle detection in undirected graphs
Essential for Kruskal's Minimum Spanning Tree

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.

Code example

Union and Find operations with Path Compression

parent = [0, 1, 2]

def find(i):
    if parent[i] == i:
        return i
    parent[i] = find(parent[i]) # Path compression
    return parent[i]

def union(i, j):
    root_i = find(i)
    root_j = find(j)
    if root_i != root_j:
        parent[root_i] = root_j
union(0, 1)
union(1, 2)
print('Root of 0 is', find(0))

vector<int> parent = {0, 1, 2};

int find(int i) {
    if (parent[i] == i)
        return i;
    return parent[i] = find(parent[i]); // Path compression
}

void unionSet(int i, int j) {
    int rootI = find(i);
    int rootJ = find(j);
    if (rootI != rootJ)
        parent[rootI] = rootJ;
}

static int[] parent = {0, 1, 2};

static int find(int i) {
    if (parent[i] == i)
        return i;
    return parent[i] = find(parent[i]); // Path compression
}

static void union(int i, int j) {
    int rootI = find(i);
    int rootJ = find(j);
    if (rootI != rootJ)
        parent[rootI] = rootJ;
}

InputUnion(0,1), Union(1,2), Find(0)

OutputRoot of 0 is 2

Example

Run the example step by step

Output

Find and Union Operations

The structure relies on two functions. Find(x) traverses up parent pointers to discover the root representative of x.

Union(x, y) merges the sets containing x and y. It does this by finding both roots, and simply making one root the parent of the other.

Find: Trace parents until you hit a node that is its own parent
Union: Point the root of one set to the root of the other
Array Implementation: parent[x] stores the parent of x

Path Compression

If a set becomes a long, tall chain, Find becomes slow (O(N)). Path Compression fixes this. Whenever we call Find(x), we take every node we visit on the way up and re-attach it directly to the root.

This flattens the paths that were traversed, making later finds much shorter. The formal near-constant amortized bound requires path compression together with union by rank or size; an individual call is not promised to be literal O(1).

Flattens tall trees during every Find call
Changes parent pointers to point directly to the root
Dramatically speeds up all future operations

Time and space costs

With both Path Compression and Union-by-Rank (attaching the shorter tree under the taller tree), the time complexity becomes the Inverse Ackermann function α(N).

The inverse Ackermann function grows so slowly that α(N) is below five for practical input sizes. Union and Find are effectively constant in applications, while their formal amortized bound remains O(α(N)). Space is O(N) for parent and rank or size arrays.

Time Complexity: O(α(N)) ≈ O(1) per operation
Space Complexity: O(N) to store parents and ranks
The guarantee is amortized across a sequence of operations

Common mistakes

A major mistake during Union(x, y) is making x point directly to y. You MUST find their roots first! It should be parent[rootX] = rootY.

Another pitfall is forgetting to initialize the parent array correctly. At the start, before any unions occur, every element must be its own parent (parent[i] = i).

Failing to find the roots before merging
Forgetting to apply path compression during Find
Incorrect initialization of the parent array