Union–find

Ten items, joined into groups pair by pair, kept in one array of ten numbers. Watch the groups grow as trees, and a search flatten them.

⋯8int find(int x)9{10    if (parent[x] != x)11        parent[x] = find(parent[x]);12    return parent[x];13}14 15bool unite(int a, int b)16{17    int ra = find(a);18    int rb = find(b);19    if (ra == rb)20        return false;21    if (rank[ra] < rank[rb]) {22        int t = ra;23        ra = rb;24        rb = t;25    }26    parent[rb] = ra;27    if (rank[ra] == rank[rb])28        rank[ra]++;29    return true;30}⋯46    const int pairs[8][2] = {47        { 0, 1 }, { 2, 3 }, { 0, 2 },48        { 4, 5 }, { 6, 7 }, { 4, 6 },49        { 0, 4 }, { 8, 9 }50    };51    for (int i = 0; i < 8; i++)52        unite(pairs[i][0], pairs[i][1]);53    print_parents("unions:");54    int r7 = find(7);55    print_parents("find(7):");56    int r3 = find(3);57    int r9 = find(9);58    print_parents("find(3), find(9):");59    int groups = 0;60    for (int i = 0; i < N; i++)61        if (parent[i] == i)62            groups++;63    printf("7 in %d, 3 in %d, 9 in %d; %d groups\n", r7, r3, r9, groups);64    return 0;

Groups that only grow

Some problems hand over pairs one at a time: these two computers are now linked, these two pixels touch, these two names mean the same thing. After each pair, the question is whether two items are in the same group yet. Groups merge but never split.

Union–find, also called a disjoint-set structure, answers that with two operations. unite(a, b) merges the groups of a and b. find(x) names x’s group. Two items are in the same group exactly when find gives the same answer for both.

The code and its cost

The forest in an array

Each group is a tree, stored in one array: parent[x] is the item above x. A root is its own parent, parent[x] == x, and the root names the group. No pointers and no allocation: ten items need forty bytes of parents. To start, every item is a root on its own:

for (int i = 0; i < N; i++) {
    parent[i] = i;
    rank[i] = 0;
}

The groups can be read straight from the array: follow parents up from any item until one points to itself. After the program’s eight unions, parent is 0 0 0 2 0 4 4 6 8 8. From 7: 7 → 6 → 4 → 0, so 7 is in group 0. From 9: 9 → 8, group 8. Two groups: 0 to 7, and 8 with 9.

find and unite

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

find climbs to the root by recursion. Returning, each call writes the root into parent[x]. So find does not only read: it rewrites the parent of every item it passed. In the clip, find(7) went four calls deep, 7, 6, 4 and 0. Returning, it wrote 0 into parent[4] (which already held 0), then into parent[6] and parent[7].

unite finds both roots. If they are the same, the items are already in one group and it returns false. Otherwise it hangs one root under the other, parent[rb] = ra, and returns true. After the program’s unions, unite(1, 3) would return false: both roots are 0.

Union by rank

Which root goes under which matters. If every union hung the old root under the newcomer, unite(0, 1), then unite(1, 2) and so on up to unite(8, 9) would build one path, 0 → 1 → 2 → … → 9, and find(0) would climb 9 steps.

Union by rank keeps a number for each root, its rank, and hangs the root of lower rank under the root of higher rank. Only when the ranks are equal does the new root’s rank grow by one. A tree of rank r then holds at least 2^r items: it got rank r by joining two trees of rank r − 1, each of at least 2^(r−1). So with n items no rank passes log₂ n, and without path compression no tree is taller than its rank. In the program the unions are all between equal ranks, and 0 ends with rank 3: (0, 1) gave it 1, (0, 2) gave it 2, (0, 4) gave it 3.

Path compression

Path compression is the rewriting find does on its way back: every item it passed now points straight at the root. After find(7), 7 is one step from 0, and so is 6; the next find(7) is a single step. Items the search did not pass keep their parents: at the end 5 still points at 4, two steps from 0, until some find passes it.

Compression changes heights but never ranks. So a rank is only an upper bound on the height of its tree. At the end, 0’s rank is 3, but its tallest path, 5 → 4 → 0, is 2 steps.

The cost and α

With both rules, m operations on n items take O(m α(n)) steps in all. α is the inverse of Ackermann’s function from indirect and nested recursion: Ackermann’s function grows so fast that its inverse is at most 4 for any n that fits in a computer. In practice, each operation costs a few steps.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic uf.c -o uf
./uf

Worked example

Without union by rank. With the newcomer always on top, the nine unions (0, 1), (1, 2), …, (8, 9) leave one path of ten items and find(0) climbs 9 steps. With union by rank, unite(0, 1) puts 1 under 0 with rank 1; every later newcomer has rank 0 and goes under 0 as well, so the tree has height 1.

Union by rank alone. Eight items, joined in rounds of equal-rank pairs: (0, 1), (2, 3), (4, 5), (6, 7) give four trees of rank 1; (0, 2), (4, 6) give two of rank 2; (0, 4) gives one of rank 3. Three rounds, height 3 = log₂ 8.

Reading the final array. parent is 0 0 0 0 0 4 0 0 8 8. Are 3 and 7 connected? 3 → 0 and 7 → 0: yes. Are 5 and 9? 5 → 4 → 0 and 9 → 8: no.

Two checks. After the unions, how many steps does find(7) climb, and how many the next time? (3, then 1.) Why does unite(1, 3) return false after the unions? (Both roots are 0.)

Where it’s used

Kruskal’s algorithm. It adds roads cheapest first and asks union–find whether a road’s two towns are already joined.

Labelling regions in images. Joining each pixel to its matching neighbours groups an image into its connected regions.

Networks as links come up. Each new link unites two groups of computers; one find each tells whether two machines can reach each other.

Compilers. Grouping names or types that have been declared equal, one equation at a time.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.