UnionFind
UnionFindは、$ N個の頂点のある無向森に対して
頂点$ u, vを含む木を接続する
頂点$ vを含む木の根を求める
頂点$ vを含む木のサイズを求める
木の個数を求める
などの操作をだいたい$ O(\alpha(N))（ほぼ定数時間）でできるデータ構造
基本的な機能
連結クエリ・連結判定・連結成分・木の個数・木のサイズ・木の根
$ \color{brown}{\bull}ABL C - Connect Cities
個数
$ \color{brown}{\bull}ABC177 D - Friends
サイズ。Friendという単語が出てくるときはUnionFindという俗説がある
$ \color{brown}{\bull}ARC106 B - Values
応用的
$ \color{blue}{\bull}ARC065 B - 連結
根
$ \color{cyan}{\bull}ABC214 D - Sum of Maximum Weights
サイズ
マージする順番を考える
$ \color{blue}{\bull}AGC005 B - Minimum Sum
実は上の問題よりも弱い
値を持つ
可換な半群を乗せることができる
Q5-1. 連結成分: $ x+y
Q5-2. 連結成分の最小値: $ \min(x, y)
Q5-5. 粘土の重さ: $ x+y
$ \color{cyan}{\bull}ABC183 F - Confluence: $ x\cup y
マージテクを使うと、ならし$ O(\log N)でマージできる
切断
定期的に人間関係をリセットしたくなるやつ
ある頂点を切り離す操作を$ O(1)程度ですることが要求される
典型
切断クエリは先読みして逆から見ると連結クエリ！
Disconnect
基本。切断クエリ
$ \color{green}{\bull}ABC217 D - Cutting Woods
切断クエリ。平衡二分木でも解けるが、UnionFindでも解ける
$ \color{cyan}{\bull}ABC120 D - Decayed Bridges
#TODO 重み付きUnionFindとかのバリエーションについても書く