UnionFindTree に関する知見の諸々 - noshi91のメモ2018/08/17 ポテンシャル付きUnionFindTreeの記述を変更し、RetroactiveUnionFind についての記述を追加しました。 2019/07/19 集合内の要素の列挙についての記述を追加しました。 はじめに UnionFindTree って知ってますか？ 競プロでは恐らく最も使用頻度の高いデータ構造だと思います*1。この記事ではプログラミングコンテストで役に立つものから全く役に立たないものまで、UnionFindTree に関するいくつかの知見を書き留めておきます。記事の最後に各内容の実装例を貼っておきます。 計算量と実装のバリエーション UnionFindTree の操作辺りの計算量が O(α(N)) であることは良く知られていますが*2、この計算量を達成するアルゴリズムはいくつかのバリエーションがあります。併合時に木の高さと大きさのどちらを指標にするかという
