readRubyで書いたUnion-Findを持っていなかったのでこの記事を書いた。Kotlinで使っていたものをRubyで書き直しただけなので、あまりRubyっぽい書き方にはなっていないかもしれない。そもそもUnion-Find木とはなんぞやということを簡単に書いておく。何グループ分けを管理するためのデータ構造で、以下の2つの操作を高速に行える。structure)に対する上記の2つの操作をUnion-Findアルゴリズムというらしく、もしかしたらデータ構造そのものをUnion-Find木と呼ぶのはおかしいのかもしれない。グループを連結成分と呼んだりもする。都市5はどのグループに属しているか?都市1と都市7は同じグループに属しているか?都市2と都市7が新たに高速道路で結ばれたのでグループを併合するそうなったとき、都市3と都市4は同じグループに属しているか?のようなクエリに高速に答えられる。find(素集合データ構造)を参照されたし。使っていたKotlinの実装はこのページを参考にした。点)この記事にある通り、併合処理の実装には2種類の方針がある。find(素集合データ構造)のスライドでもrankの方で解説されている。rankというのはグループを表す木の高さのことで、rankを管理するための専用の配列を持っておく。parent配列とrank配列の両方を管理する必要があるため少し複雑になるような気がする。sizeでやれば、最初のparent配列の初期化を工夫するだけでよく、実装がシンプルになる。副産物として、グループの大きさを簡単に取得することもできる。親ノードを探すときに、ノードの付け替えを行う経路圧縮というものを行い効率化を図っている。併合するときにはマージテクと呼ばれるものを使っている。マージテクにより、小さい方のグループが大きい方のグループのルートに繋がれるグループのサイズを知りたい場合、例えば都市4が属するグループのサイズを知りたいときは都市4がぶら下がっている親ノードは都市2であることがわかる(1はインデックスなので)都市2がぶら下がっている親ノードは都市1である(0はインデックスなので)都市1の値は負の数なのでこれがルートで、その絶対値である5がグループのサイズよって都市4が属するグループのサイズは5であることがわかる少しわかりづらいかもしれないけどこんな感じ。