読者です 読者をやめる 読者になる 読者になる

by shigemk2

当面は技術的なことしか書かない

QuickFindのソースコードをちょっといじった

アルゴリズム

アルゴリズム QuickFindをちょっといじってみた。

えっと、データ構造をマージし、グループ化するっていうやつ。

QuickFindアルゴリズムそのものの説明は下のリンクがわかりやすい。

(iwi) { 反省します - TopCoder部

流れとしては、

  1. 適当な数の配列を用意する
  2. 適当な数を2つ選び、グループ化する(union)。代表となる数は2番めに選んだ数とする。
  3. グループの代表となる数字を配列に格納する。

だいたいこんな感じ。

たとえば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 

出典

QuickFindUF.java