Disjoint Set Union (Union-Find) Explained with C++ Code

Disjoint Set Union (DSU), also called Union-Find, answers one question extremely quickly: are these two things in the same group? It also lets you merge groups as you go. That makes it perfect for problems where connections are added over time, such as roads being built between cities.

The problem

There are n cities and no roads. Roads are built one at a time. After each new road, print how many separate connected groups of cities there are, and the size of the largest group. This is CSES 1676 – Road Construction, with up to 10⁵ cities and 2 × 10⁵ roads.

Running a BFS or DFS after every road would cost O(n + m) each time, which is far too slow. DSU handles each road in almost constant time.

How DSU represents groups

Each group is a tree. Every element points to a parent, and the root of the tree points to itself. The root is the “leader” that represents the whole group. Two elements are in the same group exactly when they have the same leader.

• find(x): follow parent pointers from x until you reach the root.
• unite(a, b): find both leaders. If they differ, make one leader point to the other. The two groups are now one.

Two optimisations that make it fast

Without care, the trees can become long chains, and find becomes O(n). Two tricks prevent that:

1. Union by size. When merging, attach the smaller tree under the larger one. A node's depth only increases when its group at least doubles in size, so no tree gets deeper than log₂ n.
2. Path compression. During find, make nodes point closer to the root. The code below uses “path halving”, which points each visited node at its grandparent. Later lookups on the same path become almost instant.

With both, each operation takes amortised O(α(n)) time, where α is the inverse Ackermann function. It grows so slowly that it is at most 4 for any input that fits in the universe, so in practice it is constant.

Code (C++)

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent, sz;
    DSU(int n) : parent(n + 1), sz(n + 1, 1) {
        iota(parent.begin(), parent.end(), 0);   // everyone is their own leader
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];       // path halving
            x = parent[x];
        }
        return x;
    }
    // Returns true if a and b were in different sets.
    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
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    int components = n, largest = 1;

    while (m--) {
        int a, b;
        cin >> a >> b;
        if (dsu.unite(a, b)) {
            components--;
            largest = max(largest, dsu.sz[dsu.find(a)]);
        }
        cout << components << ' ' << largest << '\n';
    }
    return 0;
}

Each successful unite merges two groups, so the number of components drops by one. The size of the new group is stored at its leader, which makes the “largest group” easy to track.

Example

5 3
1 2
1 3
4 5

Output:

4 2
3 3
2 3

After road 1–2 there are 4 groups and the biggest has 2 cities. After 1–3, that group grows to 3. After 4–5, there are 2 groups: {1, 2, 3} and {4, 5}.

Complexity

O((n + m) · α(n)) time and O(n) memory.

Where DSU shows up

• Kruskal's minimum spanning tree. Sort edges by weight and add each one if DSU says its endpoints are not yet connected.
• Cycle detection in an undirected graph: an edge whose endpoints already share a leader closes a cycle.
• Connectivity while edges are added: answer “are u and v connected?” at any moment as the graph grows.

DSU cannot easily remove edges. If a problem deletes connections, a common trick is to process everything in reverse, turning deletions into additions.

Practice problems

• CSES 1676 – Road Construction: the problem in this post.
• CSES 1666 – Building Roads: count components and connect them.
• Codeforces 25D – Roads not only in Berland: find edges that close cycles and reuse them to join components.