Disjoint Set Union

struct DSU {
    vector<int> par, rnk;
    DSU(int n) : par(n + 1), rnk(n + 1, 1) {
        for (int i = 0; i < par.size(); i++) par[i] = i;
    }
    int find(int v) {
        return (par[v] == v) ? v : (par[v] = find(par[v]));
    }
    void uni(int a, int b) {
        a = find(a), b = find(b);
        if (a != b) {
            if (rnk[a] < rnk[b]) swap(a, b);
            par[b] = a;
            rnk[a] += rnk[b];
        }
    }
};