程式碼上色測試

struct DSU {
  int *size;
  int *parent;
  DSU(int n) {
    parent = new int[n];
    size = new int[n];
    for (int i = 0; i < n; i++) {
      parent[i] = i;
      size[i] = 1;
    }
  }
  ~DSU() {
    delete[] parent;
    delete[] size;
  }
  
  int root(int i) {
    while (parent[i] != i) {
      parent[i] = parent[parent[i]];
      i = parent[i];
    }
    return i;
  }
  
  void join(int a, int b) {
    int ra = root(a);
    int rb = root(b);
    
    if (ra == rb) return ;

    if (size[ra] < size[rb]) {
      parent[ra] = rb;
      size[rb] += size[ra];
    }
    else {
      parent[rb] = ra;
      size[ra] += size[rb];
    }
  }
};