leetcode-go/poj/1988.cube-stacking/main.cc

#include <cstdio>

using namespace std;

const int N = 30000;

struct UF {
  int id[N + 1];
  int sz[N + 1];
  int ud[N + 1];
};

UF uf;

int find(int i) {
  if (i == uf.id[i]) return i;
  int j = find(uf.id[i]);
  uf.ud[i] += uf.ud[uf.id[i]];
  uf.id[i] = j;
  return j;
}

void move(int i, int j) {
  i = find(i);
  j = find(j);
  if (i == j) return;
  uf.ud[i] = uf.sz[j];
  uf.id[i] = j;
  uf.sz[j] += uf.sz[i];
}

int main() {
  int p;
  scanf("%d", &p);
  for (int i = 1; i <= N; i++) {
    uf.id[i] = i;
    uf.sz[i] = 1;
    uf.ud[i] = 0;
  }
  char op[2];
  for (int i = 0, x, y; i < p; i++) {
    scanf("%s", op);
    if (op[0] == 'C') {
      scanf("%d", &x);
      find(x);
      printf("%d\n", uf.ud[x]);
    } else {
      scanf("%d %d", &x, &y);
      move(x, y);
    }
  }
  return 0;
}