Disjoint sets (union-find)

Introduction

Some questions are only about groups: are these two computers on the same network? Are these two people in the same circle of friends? Which pixels form one region of an image? A disjoint-set structure, usually called union-find, answers them with two operations:

• find(x): which group is x in? Each group is named by one member, its root.
• union(a, b): join a's group and b's group into one.

Two items are in the same group exactly when find(a) == find(b).

Some questions do not care about the path between two items, only about whether one exists. Union-find answers that with a single array, and it is far faster than running a graph search for every question.

How it works

A forest in an array

Each group is a tree, stored in one array: parent[x] is x's parent, and a root is its own parent. At the start everyone is alone: parent[i] = i.

#include <stdio.h>

int parent[6];

int find(int x) {
    while (parent[x] != x) x = parent[x];   // climb to the root
    return x;
}

void unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra != rb) parent[ra] = rb;          // hang one root under the other
}

int main(void) {
    for (int i = 0; i < 6; i++) parent[i] = i;   // everyone starts alone
    unite(0, 1);
    unite(2, 3);
    unite(1, 3);
    printf("0 and 2: %s\n", find(0) == find(2) ? "same group" : "different");
    printf("0 and 4: %s\n", find(0) == find(4) ? "same group" : "different");
    return 0;
}

find climbs parent links to the root. unite finds both roots and hangs one under the other; joining any two other members would break the trees. This works, but it can be slow: unite 0 with 1, then 1 with 2, then 2 with 3, … and the tree becomes a long chain, so find takes O(n).

Where it is used

• Kruskal's minimum spanning tree: take edges from cheapest up, and skip an edge when both ends are already in one group (it would make a cycle). See the Minimum spanning trees lesson.
• Counting connected components while edges arrive one by one: start with n groups and subtract one for every union that joins two different groups.
• Percolation and image regions: join neighbouring cells of the same colour.

Union-find cannot split a group again. If edges are deleted, rebuild, or use a different structure.

Syntax

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

Example

Union by size: hang the smaller tree under the bigger one. A node then only gets deeper when its tree at least doubles in size, so no tree is deeper than log₂ n.

Path compression: while find climbs to the root, make every node on the way point straight at the root. The next find from any of them takes one step.

#include <stdio.h>

#define N 8
int parent[N], size[N];

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

int unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return 0;                 // already in one group
    if (size[a] < size[b]) {              // union by size:
        int t = a;                        // a is the bigger tree
        a = b;
        b = t;
    }
    parent[b] = a;
    size[a] += size[b];
    return 1;
}

int main(void) {
    int groups = N;
    for (int i = 0; i < N; i++) {
        parent[i] = i;
        size[i] = 1;
    }
    int edges[6][2] = {{0, 1}, {2, 3}, {1, 3}, {4, 5}, {3, 0}, {6, 7}};
    for (int e = 0; e < 6; e++)
        if (unite(edges[e][0], edges[e][1])) groups--;
    printf("groups: %d\n", groups);
    printf("size of 0's group: %d\n", size[find(0)]);
    return 0;
}

With both, a sequence of m operations on n items costs O(m · α(n)), where α is the inverse Ackermann function. α(n) is at most 4 for any n that fits in the universe, so each operation is constant time in practice.

Line by line

1. parent and size are arrays, and a root is its own parent.
2. find follows parents up to the root and, on the way back, points each node straight at it.
3. unite replaces a and b by their roots, and returns 0 if they are already in one group.
4. The swap makes sure that a is the larger tree. The smaller tree is then hung under it, and its size is added.
5. main starts with 8 separate groups and joins pairs from the edges array, subtracting one for each real union.
6. The pair 3, 0 joins nothing new, so it does not count. The program prints the number of groups, then the size of 0's group.

Expected result

groups: 3
size of 0's group: 4

In the real world

Kruskal's algorithm uses union-find to build the cheapest network that connects every town. Image editors use it to find regions of one colour, and networks use it to tell whether two machines are connected.

Common mistakes

• Writing parent[a] = b instead of parent[find(a)] = find(b): that cuts a out of its old tree.
• Counting a union that joined a group with itself: check find(a) != find(b) first.
• Comparing parent[a] == parent[b] to test "same group": only the roots tell you that.

Best practices

• Always unite the roots, and never the original items.
• Count a union only when it actually joined two groups.
• Use find, never parent, to compare groups.

Summary

Union-find keeps groups as trees in an array. With union by size and path compression, each operation is close to constant time, which makes it ideal for connectivity that only ever grows.

Mark lesson complete