← all categories

Dsu 191d69c2

Disjoint set union with path compression + union by size.

Time: O(\alpha(n)) amortized per operation. tested

content/graphs/dsu.h

struct DSU {
    vector<int> par, sz;

    DSU(int n) : par(n), sz(n, 1) { iota(par.begin(), par.end(), 0); }

    int find(int u) { return par[u] == u ? u : par[u] = find(par[u]); }

    bool unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;
        if (sz[u] < sz[v]) swap(u, v);
        par[v] = u;
        sz[u] += sz[v];
        return true;
    }
};