アルゴリズム QuickFindをちょっといじってみた。
えっと、データ構造をマージし、グループ化するっていうやつ。
QuickFindアルゴリズムそのものの説明は下のリンクがわかりやすい。
流れとしては、
- 適当な数の配列を用意する
- 適当な数を2つ選び、グループ化する(union)。代表となる数は2番めに選んだ数とする。
- グループの代表となる数字を配列に格納する。
だいたいこんな感じ。
たとえば10個の要素の配列があったとして、
union(8,0);
ってやると、2つの要素には0が格納される。
改造ソースコード
shigemk2/quick-find-algo · GitHub
出典のコードは、配列の要素数とか、グルーピングする数字などを標準入力で
入力しているね。
でも、ループの終わらせ方が分からないし、どの要素がどのグループに入っているのかも
分からないのでとりえあず勝手に要素数を決めて勝手にグルーピングさした。
$ java QuickFindUF 1 3 9 components 8 5 8 components 9 5 7 components 5 4 6 components 7 0 5 components 0 3 4 components 4 components 3 3 2 3 4 4 6 3 4 4
