Fully Retroactive Union Find

個人的メモ

Demaine 先生の資料 に fully retroactive union find は $\O (\log m)$ ($m$ は更新の回数) でできると書いてあり, 考えてみると Link Cut Tree を用いると(order-maintenance パートを無視した場合) ならし $\O (\log n)$ でできることが分かった (資料自体には priority_queue の partial retroactive の説明が分かりやすく書いてある).
結局 fully retroactive union find は unite 関数では頂点どうしを link でつなぎ, same 関数では "頂点どうしが現在のバージョンにおいて同じ連結成分に入っているか", "もしそうなら頂点間のパス上の辺の時刻の最大値が $\_ time$ 以下であるか" を見ることで時刻 $\_ time$ の直後において $2$ つの頂点が同じ連結成分に入っているかどうかを判定することが可能.
注意として unite 関数で頂点どうしをつなぐときにすでに $2$ つの頂点が同じ連結成分に属する場合はそのパス上の辺の時刻の最大値をみて $\_ time$ より大きければその辺を cut して付け替える.
実装を容易にするために頂点だけでなく辺もノードとして保持している.