Union-Find（素集合データ構造）とは？
Union-Find（素集合データ構造）とは、互いに素な集合の集まりを管理し、2つの集合の併合（union）と、ある要素がどの集合に属するかの検索（find）を高速に行うデータ構造。各集合を根付き木で表し、経路圧縮とランクによる併合を併用すると1操作がほぼ定数時間になる。
ゆにおんふぁいんど
Union-Find（素集合データ構造）の意味
互いに素な集合の集まりを管理し、2つの集合の併合（union）と、ある要素がどの集合に属するかの検索（find）を高速に行うデータ構造。各集合を根付き木で表し、経路圧縮とランクによる併合を併用すると1操作がほぼ定数時間になる。
Union-Find（素集合データ構造）の具体例
ネットワークの連結判定に使う。ノード間のリンクを1本ずつunionしていき、最後に全ノードのfindが同じ根を返せば全体が連結していると分かる。最小全域木を求めるクラスカル法でも、辺を加える際の閉路検出に用いる。
Union-Find（素集合データ構造）は試験でどう引っ掛けられる？
併合はできるが分割（一度つないだ集合を元に戻す操作）は基本的にできない。経路圧縮を入れないと木が縦に伸びてfindがO(n)へ劣化する点も、実装上の落とし穴として問われる。
Union-Find（素集合データ構造）と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。