読者です 読者をやめる 読者になる 読者になる

誤読

文字通りくそコード

Union-Find with deletions

謎のデータ構造を見つけてしまった。実装したくなかったが、してしまった。後悔しかしていない。

UnionFindといえば競プロerであればほとんどの人が知ってると思われるが、あれはUniteとFindはあってもある要素をフリーにするという操作ができない。

UF木の葉以外を削除しようとすると計算量が増えてしまうのは想像がつくと思う。

そこでUnion-Find with Deletionsというのがあって、これを使うとUniteをO(A(n)),FindをO(A(n)),DeleteをO(1)でできるようになっておいしい。
(追記)論文でUniteがO(1)なのは集合をしていしてUniteする実装だからで、要素を指定してそれらの属するグループを併合するっていうのはFindを挟む必要があるのでO(A(n))になっているだけです。


主なアイデア

1.要素の部分と木構造の部分を切り離して木のノードが要素を持つという形にすると、削除したいノードの持つ要素とその木の中での葉の要素をswapしてから葉を消せばよい。

2.入りだけのオイラーツアーを持つことで葉のノードがわかる。

3.経路圧縮でいつものやつじゃなくてTarjan and Jan van Leeuwenが考えた経路圧縮を使いましょう。(ノードを親の親にくっつける)

説明能力が皆無なのでこの論文とこのスライドを合わせて読むと実装できます(大嘘)


この論文の通りにだと実装できなかったんですけど、アレンジを加えて頑張りましょう💢💢💢💢💢💢💢💢

↓ぼくのじっそう(ゴミ)

[C++] class UFNode; class LNode { public: UFNode *Myval; LNode *Prev, *Next; L - Pastebin.com


普通に汎用性高そう(小並感)なので今後の競プロ界のトレンド間違いなしだよ

せっかく無限に時間を溶かして書いたのに使う問題とか一切見当たらないため非常にアレなので使えそうなのがあったらほんと教えてください。

HOJにverify問投稿しようかな…