并查集

可撤銷并查集

參考：ACM——可撤銷并查集教程

普通并查集只能加邊而不能刪邊。

可撤銷并查集支持撤銷上一次操作。

不能路徑壓縮，需要按秩合并。（則樹高是 \(\log n\) 的）

每個點維護 \(fa,siz\) 等信息，撤銷上一次操作時，修改 \(fa_u\) 和 \(siz_{fa_u}\) 即可。

所以可撤銷并查集 find() 是 \(O(\log n)\) 的，撤銷是 \(O(1)\) 的。