素集合の要素の列挙と併合 (単方向循環リスト)

概要

以下の 2 種類のクエリを処理します。

$\texttt{get} ( x )$
$x$ と同じ集合の要素を全て列挙します。
時間計算量 $\Theta ( x$ を含む集合の要素数 $)$
$\texttt{unite} ( x , y )$
$x , y$ がそれぞれ含まれる集合同士を併合します。
$x , y$ が同じ集合に含まれているとバグりますが検出はできません。
時間計算量 $\Theta ( 1 )$

理論

同一集合内のノードを片方向循環リストで数珠つなぎにします。

実装では配列を用いて、要素 $i$ の次の要素を $\texttt{next} \lbrack i \rbrack$ で表現するとよいと思います。
$\texttt{unite}$ は $\texttt{swap} ( \texttt{next} \lbrack x \rbrack , \texttt{next} \lbrack y \rbrack )$ を行うだけです。