紀(jì)念一下，跟我生日一樣的題目。
思路：
這題可以用并查集來做，也是挺取巧的。
每個(gè)棧看做是一個(gè)集合，用一個(gè)數(shù)組記錄棧中元素離棧底的距離，一個(gè)數(shù)組記錄每個(gè)棧底元素對(duì)應(yīng)的棧頂?shù)脑亍?br>對(duì)于移動(dòng)操作，只需要合并集合，然后更改棧頂元素?cái)?shù)組就行了。
用了棧寫的路徑壓縮，代碼跑到230ms。不知道那些100ms是怎么搞出來的。。真的有什么神奇技巧嗎。
#include <stdio.h>
#define MAX_N 30032
int top[MAX_N];
struct set_node 
{
int parent, dis;
};
struct set_node set[MAX_N];
__inline int find(int idx)
{
static int stk[MAX_N], sp, i;
for (sp = 0; set[idx].parent; sp++) {
stk[sp] = idx;
idx = set[idx].parent;
}
for (sp--; sp >= 0; sp--) {
i = stk[sp];
set[i].dis += set[set[i].parent].dis;
set[i].parent = idx;
}
return idx;
}
int main()
{
int p, a, b;
char op[16];
freopen("e:\\test\\in.txt", "r", stdin);
for (a = 0; a < MAX_N; a++)
top[a] = a;
scanf("%d", &p);
while (p--) {
scanf("%s%d", op, &a);
if (op[0] == 'M') {
scanf("%d", &b);
a = find(a);
b = find(b);
set[a].parent = top[b];
set[a].dis = 1;
top[b] = top[a];
} else {
find(a);
printf("%d\n", set[a].dis);
}
}
return 0;
}