Как реализовать DSU со сжатием путей и объединением по рангу, чтобы получить почти O(1)?

DSU держит лес деревьев: каждый элемент знает своего «родителя», корень — представитель множества. Две оптимизации:

1. Сжатие путей в find: по пути к корню перевешиваем все вершины напрямую на корень.
2. Объединение по рангу (приближённая высота): меньшее дерево подвешиваем под большее, чтобы не растить глубину.

struct DSU {
    vector<int> p, rnk;
    DSU(int n) : p(n), rnk(n, 0) { iota(p.begin(), p.end(), 0); }
    int find(int x) {
        while (x != p[x]) x = p[x] = p[p[x]]; // path halving
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (rnk[a] < rnk[b]) swap(a, b);
        p[b] = a;
        if (rnk[a] == rnk[b]) ++rnk[a];
        return true;
    }
};

Я использовал path halving (p[x] = p[p[x]]) — он без рекурсии и без второго прохода, амортизированно так же хорош, как полное сжатие. С обеими оптимизациями амортизированная сложность одной операции — O(α(n)), где α — обратная функция Аккермана (для всех реальных n ≤ 4). По памяти O(n). unite возвращает false, если уже в одном множестве — удобно для подсчёта числа объединений в Краскале.