![見出し画像](https://assets.st-note.com/production/uploads/images/95383074/rectangle_large_type_2_24502f24b2ca845dcb4ea1c5f61d11ed.png?width=1200)
今日のIT短歌059 #Union-Find
あなたとの共通点を探したい。まずはUnion-Findつくる。
素集合データ構造
素集合データ構造(そしゅうごうデータこうぞう、英: disjoint-set data structure)は、データの集合を素集合(互いにオーバーラップしない集合)に分割して保持するデータ構造。このデータ構造に対する以下の2つの便利な操作をUnion-Findアルゴリズムと呼ぶ。
Find: 特定の要素がどの集合に属しているかを求める。2つの要素が同じ集合に属しているかの判定にも使われる。
Union: 2つの集合を1つに統合する。
これら2つの操作をサポートしているため、素集合データ構造は「Union-Findデータ構造」あるいは「Merge-Find集合」とも呼ばれる。