這題算是半道水題了。但代碼實(shí)現(xiàn)還是有點(diǎn)麻煩，所以還是值得一寫。
同一堆的方塊位于同一個(gè)集合。
每個(gè)方塊保存一個(gè)值：距離底部的高度
作為集合根部節(jié)點(diǎn)的方塊保存一個(gè)值：這堆方塊的高度
在并查集的合并以及查找過程中需要維護(hù)這兩個(gè)值。
#include <stdio.h>
#define N 65536
int P, parent[N], pos[N], top[N], stk[N];
int fs(int idx)
{
int i;
for (i = 0; parent[idx] != idx; i++) {
stk[i] = idx;
idx = parent[idx];
}
for (i--; i >= 0; i--) {
pos[stk[i]] += pos[parent[stk[i]]];
parent[stk[i]] = idx;
}
return idx;
}
int main()
{
char op[16];
int x, y, rx, ry;
for (x = 0; x < N; x++) {
top[x] = 1;
parent[x] = x;
}
scanf("%d", &P);
while (P--) {
scanf("%s", op);
if (*op == 'M') {
scanf("%d%d", &x, &y);
rx = fs(x);
ry = fs(y);
if (rx != ry) {
parent[rx] = ry;
pos[rx] = top[ry];
top[ry] += top[rx];
}
} else {
scanf("%d", &x);
fs(x);
printf("%d\n", pos[x]);
}
}
return 0;
}