DSU (Union-Find)

O(α(n)) per operation

Maintains a collection of disjoint sets under two operations: find which set an element belongs to, and merge two sets. With path compression and union by size both are effectively constant time. The standard structure for connectivity, Kruskal's MST, and grouping problems.

// use it on

CSES: Road Construction ↗

After each added road, report the number of connected components and the size of the largest one. That is exactly what unite() and the size array maintain.

// the code

struct DSU {
    vector<int> parent, size;
    DSU(int n) : parent(n), size(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) x = parent[x] = parent[parent[x]];
        return x;
    }
    bool unite(int a, int b) {  // returns false if already connected
        a = find(a), b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
        return true;
    }
};