uniolympiads Ελληνικά

Disjoint set union (DSU)

Merge sets and ask whether two elements are in the same one, in almost constant time per operation.

When

Edges arrive one by one and you ask about connectivity: "are aa and bb connected?", "how many components are there?", "how big is the largest?". It is also half of Kruskal.

The idea

Each set is a tree, and its representative is the root. find climbs to the root. unite hangs one root below the other.

Two improvements keep the trees almost flat:

  1. Path compression. After each find, every node on the path points straight to the root.
  2. Union by size. The smaller tree is hung below the larger one. The height then stays O(log⁡n)O(\log n) even without compression.

Together they give O(α(n))O(\alpha(n)) per operation, where α\alpha is the inverse Ackermann function. In practice this is a constant, at most 4 for any nn you will see.

find here is iterative. The recursive version is shorter, but on a chain of 10610^6 nodes before the first compression it overflows the stack. The test checks exactly that.

Pitfalls

  • unite returns whether a merge happened. That is what you need to count components (start from nn and subtract one on each success) or to detect cycles.
  • A DSU does not delete edges. If the problem removes edges, try running it backwards, adding them.

Code

No main: it goes below the #include lines, using namespace std and using ll = long long.

cpp/dsu.cpp
// Disjoint set union with path compression and union by size.
// Almost O(1) per operation (inverse Ackermann).

struct DSU {
    vector<int> parent;
    vector<int> sz;

    DSU(int n) : parent(n), sz(n, 1) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        int root = x;
        while (parent[root] != root) {
            root = parent[root];
        }
        // Second pass: point every node on the path straight to the root.
        while (parent[x] != root) {
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    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);
        }
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }

    bool same(int a, int b) {
        return find(a) == find(b);
    }

    int size(int x) {
        return sz[find(x)];
    }
};

Tested on 501 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Practice on CSES

In order: the first is the plain application, the rest need a twist.

More in the USACO Guide

In English, with more problems per level.