src/DataStructure/QuickFind.hpp
概要
素集合データ構造のマージを高速化するテクニック。
n要素の集合のマージを何度も行う際に、サイズの小さい方を大きい方にマージすることでのべ移動回数がO(n log n)回で抑えられる。
これは、各要素に注目すると、別の集合に移動されるたびに属する集合のサイズが2倍以上になるのでO(log n)回しか移動されないことからわかる。
データをマージする一般的なテク(通称、マージテク)とも呼ばれる。
名前はiwiwiさんのブログに由来するが、消えてしまった…。
アカデミア用語はWeighted-Union Heuristic。
Verified with
Code
Back to top page