A了,但是对时间复杂度有疑问
查看原帖
A了,但是对时间复杂度有疑问
684131
VainSylphidElena楼主2023/4/16 20:38

我按照OI wiki的写法写了按秩合并

但是我发现OI wiki的代码按秩合并不完全是按秩合并,不论树高是否相等都取较大的秩加一

于是我写的时候改成了标准的按秩合并并加了快速读写,结果开O295pts不开O268pts

于是我改成了启发式合并,结果A了,我又复制了OI wiki的写法,也A了。

看到讨论区还有人写按下标合并都过了,所以按秩合并的复杂度有什么问题吗,还是我写假了。

顺便一提你谷并查集模板题解有不少把启发式合并甚至裸合并说成按秩合并的……虽然都是上古题解了但也不能误导MnZn罢。

2023/4/16 20:38
加载中...