Persistent UnionFindって?

過去の情報を取得できるUnionFindです.

仕組み

1つ目の方法として, 永続配列の上でUnionFindを実装する, という方法があります. これで各種クエリがならし$O(\log N\alpha(N))$です.

ここでは違う方法で実装します.
一旦「経路圧縮していないUnionFindの操作」を見てみましょう.

まずはこちら, 何もしていないUnionFindです.

AとBの集合をマージしましょう. マージした順に矢印に番号を書きます.

DとEもマージします.

AとC, AとDをマージします.

このように, 各操作では「マージに対応する辺の追加」以外の操作は行われていないことが分かります.

最後の状態の時, 番号が3以上の辺を無視してみると (図では点線にしてみます)

見比べると, DとEをマージした段階までの状態と一致します. ということで, こういう風に辺に操作の番号を付けて, 適切に無視することで過去の情報を見ることが出来ます.

上記をそのまま実装します. UnionFindを実装したことがあれば楽々ですね.

いかがでしたか?

明日も永続データ構造シリーズをします.