并查集
并查集
可撤銷并查集
普通并查集只能加邊而不能刪邊。
可撤銷并查集支持撤銷上一次操作。
不能路徑壓縮,需要按秩合并。(則樹高是 \(\log n\) 的)
每個點維護 \(fa,siz\) 等信息,撤銷上一次操作時,修改 \(fa_u\) 和 \(siz_{fa_u}\) 即可。
所以可撤銷并查集 find() 是 \(O(\log n)\) 的,撤銷是 \(O(1)\) 的。
本文來自博客園,作者:wing_heart,轉載請注明原文鏈接:http://www.rzrgm.cn/wingheart/p/19132306

浙公網安備 33010602011771號