題意：有30000個(gè)木塊，編號(hào)從1到30000，然后有兩種操作M a b，把木塊a所在的堆塊放到木塊b所在的堆塊上，操作C a，詢問(wèn)木塊a下面有多少個(gè)木塊。
題解：用1個(gè)數(shù)組s[i]存木塊i所在堆塊1共有多少個(gè)木塊，由于要求木塊i下面有多少個(gè)木塊，所以再添加1個(gè)數(shù)組dis[i]存木塊i到根節(jié)點(diǎn)有多少個(gè)木塊，這樣res = s[i]-dis[i]⑴。dis數(shù)組更新放在尋覓根結(jié)點(diǎn)遞歸的后面，由于要先更新父親的再更新自己的。
#include <stdio.h>
const int N = 30005;
char str[5];
int p, pa[N], s[N], dis[N];
int get_parent(int x) {
if (x != pa[x]) {
int f = pa[x];
pa[x] = get_parent(pa[x]);
dis[x] += dis[f];
}
return pa[x];
}
int main() {
int t;
for (int i = 0; i <= N; i++) {
pa[i] = i;
s[i] = 1;
dis[i] = 0;
}
scanf("%d", &t);
while (t--) {
scanf("%s", str);
if (str[0] == 'M') {
int a, b;
scanf("%d%d", &a, &b);
int px = get_parent(a);
int py = get_parent(b);
pa[py] = px;
dis[py] = s[px];
s[px] += s[py];
}
else {
int a;
scanf("%d", &a);
int px = get_parent(a);
printf("%d
", s[px] - dis[a] - 1);
}
}
return 0;
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
