Disjoint Set Union (DSU)

class DSU {
  vector<int> parent, sz;
public:
  DSU(int n) {
    parent.resize(n);
    sz.resize(n, 1);
    for (int i = 0; i < n; i++) parent[i] = i;
  }
  int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
  }
  void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    parent[b] = a;
    sz[a] += sz[b];
  }
  bool same(int a, int b) { return find(a) == find(b); }
  int size(int x) { return sz[find(x)]; }
};