Disjoint set union

A disjoint set union (DSU) keeps elements split into groups (disjoint sets) that merge over time, and tells quickly whether two elements are in the same group. If the groups never change, one search finds them all, as in connected components.

It is for groups that only grow: roads between towns are built one at a time, and between the builds someone asks whether two towns are connected yet. A new depth-first search per question costs O(n + m); a DSU answers in practically constant time.

How it works

Each town has a parent, one town of its own group, drawn as an arrow. One town in each group is its own parent: the group's root. Following the arrows from any town ends at its root. The arrows are not roads; they only record the group.

Fig. 1. Each town points at a town of its group. Following the arrows from town 4 leads to town 1, the root.

Find and union

The first operation, find$(v)$, follows the arrows from $v$ and returns its root. The second, union$(a,b)$, finds the roots of $a$ and $b$ and, if they differ, points one at the other. Two towns are in the same group when find gives them the same root.

This fits only a relation that passes along: if $a$ is with $b$ and $b$ with $c$, then $a$ is with $c$. Friendship doesn't. A DSU also can't split a group when a road closes.

Union by size

If union always points the root of $a$ at the root of $b$, the unions of town 1 with 2, 3, …, 8 build a chain, and with $n$ towns the finds walk about n^2 / 2 arrows.

The first rule is union by size. Keep the size of each group at its root, in sz, and point the root of the smaller group at the root of the larger one.

Fig. 2. The same seven unions, in a fixed order (top) and by size (bottom).

A town moves one arrow further from its root only when its group joins a group at least as large, so its group at least doubles. That happens at most \log_2 n times, and find is O(\log n).

Path compression

The second rule is path compression. When find has reached the root, it points every town it passed straight at the root. A recursive find does this in one line, writing the root into each parent on the way back.

Fig. 3. The chain before (top) and after (bottom) find(1).

A full run

Let's run a few unions on 8 towns, with gets in between, where get $a$ $b$ asks whether $a$ and $b$ are in one group.

Every town is its own root, in a group of size 1.

union 1 2: the roots 1 and 2 have groups of the same size, 1, so 2 is pointed at 1, and the group of 1 has 2 towns.

union 3 4: the roots 3 and 4 have groups of the same size, 1, so 4 is pointed at 3, and the group of 3 has 2 towns.

union 2 4: the roots 1 and 3 have groups of the same size, 2, so 3 is pointed at 1, and the group of 1 has 4 towns.

union 5 6: the roots 5 and 6 have groups of the same size, 1, so 6 is pointed at 5, and the group of 5 has 2 towns.

get 2 6: find(2) gives 1 and find(6) gives 5, so the answer is NO.

union 7 6: the root 7 has a group of 1 and the root 5 a group of 2, so 7 is pointed at 5, and the group of 5 has 3 towns.

get 4 2: find(4) gives 1 and find(2) gives 1, so the answer is YES. Path compression points town 4 straight at 1.

union 6 4: the root 5 has a group of 3 and the root 1 a group of 4, so 5 is pointed at 1, and the group of 1 has 7 towns.

get 7 8: find(7) gives 1 and find(8) gives 8, so the answer is NO. Path compression points town 7 straight at 1.

1/10

Fig. 4. Step through the operations with the buttons. Roots are green with their group size beside them. A blue arrow is new: one root now points at another. A red arrow was moved by path compression, and its old arrow is grey.

After the nine operations, towns 1 to 7 are one group with root 1, and town 8 is alone. The three gets answer NO, YES and NO. Path compression moved two arrows on the way: town 4's in get 4 2 and town 7's in get 7 8.

With both rules, $m$ operations on $n$ towns take O(m \cdot \alpha(n)) time, where $\alpha$ is the inverse Ackermann function, at most 4 for any $n$ in a contest. The memory is two arrays of n + 1 numbers.

In C++

The standard library has no DSU. Two vectors hold the parent and the group size of each town.

The program reads n and m (1 \le n, m \le 5 \cdot 10^5), then m lines union u v or get u v. For each get it prints YES if u and v are in one group and NO otherwise. The run above has this input:

8 9
union 1 2
union 3 4
union 2 4
union 5 6
get 2 6
union 7 6
get 4 2
union 6 4
get 7 8

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> parent, sz;

// find: the root of v's group
int find(int v) {
    if (parent[v] == v) return v;
    return parent[v] = find(parent[v]);   // path compression
}

// union: merge the groups of a and b; false if they were one group already
bool unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return false;
    if (sz[a] < sz[b]) swap(a, b);        // union by size: a is the larger root
    parent[b] = a;
    sz[a] += sz[b];
    return true;
}

int main() {
    int n, m;
    cin >> n >> m;
    parent.resize(n + 1);
    sz.assign(n + 1, 1);
    for (int v = 1; v <= n; v++) parent[v] = v;   // every town is its own group

    for (int i = 0; i < m; i++) {
        string op;
        int u, v;
        cin >> op >> u >> v;
        if (op == "union") {
            unite(u, v);
        } else {
            cout << (find(u) == find(v) ? "YES" : "NO") << '\n';
        }
    }
}

The size of the group of v is sz[find(v)]: only roots keep correct sizes. The number of groups is n minus the number of calls to unite that returned true.

Examples of use

Components while roads arrive

Some problems add roads one at a time and ask after each how many connected components there are, or how large the largest is. Count the groups as above and keep a running maximum of sz[find(u)]. A union that returns false means the new road closes a cycle.

Kruskal's algorithm

To connect all towns at the smallest total cost, Kruskal's algorithm sorts the roads by cost and takes each road whose ends are still in different groups, exactly when unite returns true. The sort, O(m \log m), sets the running time.

Deletions backwards

When roads close one at a time and all closures are known in advance, run them backwards. Start with the roads that never close and add the closed roads back with unite, the last closed first. Before a road goes back, the groups are those right after it closed, so record the answer then, and print the answers in reverse order at the end.

Common mistakes

• Comparing or linking towns instead of their roots, as in parent[a] == parent[b], which can say NO for two towns of one group. Compare find(a) == find(b).

• Merging a group with itself, which adds its size to sz a second time. Stop when the roots are equal, as if (a == b) return false does.

• Reading the size at a town that is not a root, where sz is out of date. Read sz[find(v)].

• Leaving out union by size, so the first recursive find on a chain of 5 \cdot 10^5 towns goes that many calls deep and can overflow the stack. With union by size it is at most 19 calls.

Similar structures

Depth-first search labels the components of a fixed graph in O(n + m) and can give a route; breadth-first search gives the shortest one. A DSU stores no roads, so it can do neither. An adjacency list beside it keeps the roads when they are needed.

Practice