通过本题,我学会了一种神奇的东西——并查集
这题让我WA了两次,总结一下错误原因,希望能够帮到大家(做题前别看啊QAQ)
①要从father那里更新的时候,father一定不能经过路径压缩(不然你每次加的都是0),但是一定要求出对应的参数(比如father之前有多少个战舰);
②下面pre表示它之前有多少艘战舰,size表示联通块大小:
pre[fx] += size[fy];
size[fy] += size[fx];
上面这个东西是对的,但是如果交换一下顺序的话……就死了
③不管怎么样,在做merge或query之前,一定要做路径压缩!
④我太菜了,不知道询问的两艘战舰哪个在前,哪个在后……所以要abs一下啊。
QAQ