Disjoint-set data structure
Program
Description
共通の元を持たない二つの集合のことを「互いに素である」という。
どの二つの集合も互いに素であるような集合族（集合の集合）のことを、「素集合族（Disjoint sets）」という。
素集合族を効率よく扱うために、「disjoint-set forest」というデータ構造がある。このデータ構造は以下の操作をサポートする。
- Making new sets
- Finding set representatives
- Merging two sets
Making new sets
素集合族に元（自身をただ一つの元とする集合）を追加する。いずれかの集合にすでに存在していた場合は何もしない。
Finding set representatives
ある元が属する集合の代表元を返す。この操作により、ある二つの元が同じ集合に属しているかを、代表元での比較により行える。
Merging two sets
ある二つの元が属する素集合を結合する。
Examples
Reset: => {}
Add: 0 => {{0}}
Add: 1 => {{0}, {1}}
Add: 2 => {{0}, {1}, {2}}
Union: 0, 2 => {{0, 2}, {1}}
Add: 3 => {{0, 2}, {1}, {3}}
Find: 0 => 0
Find: 2 => 0
Find: 3 => 3
Union: 2, 3 => {{0, 2, 3}, {1}, {3}}
Find: 2 => 0
Find: 3 => 0