Union-Find（素集合データ構造）入門 - 経路圧縮とunion by sizeで連結性を高速に管理する
約32分
要素のグループ分けを管理するUnion-Find（素集合データ構造 / DSU）を解説します。find・union・sameという3つの基本操作、森による表現、素朴な実装がO(n)に劣化する理由、経路圧縮とunion by sizeという2つの最適化、Tarjanが示したならしO(α(n))という計算量、クラスカル法・連結成分の数え上げ・グリッドの島の数・サイクル検出・重み付きUnion-Findといった応用、各言語の標準ライブラリ事情まで、実際に動くPythonコードで整理します。