并查集

class UnionFind {
public:
  UnionFind(int n) : parent(n), rank(n, 0) {
    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 x, int y) {
    int a = find(x);
    int b = find(y);
 
    if (a == b) { return; }
 
    if (rank[a] < rank[b]) {
      parent[a] = b;
    } else if (rank[a] > rank[b]) {
      parent[b] = a;
    } else {
      parent[b] = a;
      rank[a]++;
    }
  }
 
private:
  vector<int> parent;
  vector<int> rank;
};