Disjoint Set Union

struct DSU {
    vector<int> fa;
    void init(int n) {
        fa.assign(n+1, -1);
    }
    int root(int x) {
        return fa[x] < 0 ? x : fa[x] = root(fa[x]);
    }
    void unite(int u, int v) {
        u = root(u);
        v = root(v);
        if (u == v) return;
        if (fa[u] > fa[v]) swap(u,v);
        fa[u] += fa[v];
        fa[v] = u;
    }
    void uniteRoot(int u, int v) {
        if (fa[u] > fa[v]) swap(u,v);
        fa[u] += fa[v];
        fa[v] = u;
    }
};