告诫后人
查看原帖
告诫后人
87064
ducati楼主2020/10/20 18:08

通过本题,我学会了一种神奇的东西——并查集

这题让我WA了两次,总结一下错误原因,希望能够帮到大家(做题前别看啊QAQ)

①要从fatherfather那里更新的时候,fatherfather一定不能经过路径压缩(不然你每次加的都是00),但是一定要求出对应的参数(比如fatherfather之前有多少个战舰);

②下面prepre表示它之前有多少艘战舰,sizesize表示联通块大小:

pre[fx] += size[fy];
size[fy] += size[fx];

上面这个东西是对的,但是如果交换一下顺序的话……就死了

③不管怎么样,在做mergemergequeryquery之前,一定要做路径压缩!

④我太菜了,不知道询问的两艘战舰哪个在前,哪个在后……所以要absabs一下啊。

QAQ

2020/10/20 18:08
加载中...