「グループを作ろう！」のやり直し

CodeIQで id:hyuki さんが出題された「グループを作ろう！」を解いてみたのですが、

でしたので、復習してみました。間違いの原因は、両辺のニックネームが既出だった場合が条件として漏れていたことでした。以下のプログラムで模範解答と同じ結果を得ることができますが、追加した部分の処理(両辺のニックネームが既出だったとき)では、ハッシュに登録されている全てのニックネームを調べ、右辺のニックネームの所属するグループ番号を左辺のニックネームの所属するグループ番号に付け替えるという処理を行なっているので、データ数が増えるにしたがって効率が悪くなります。解説で紹介されている「Union Findアルゴリズム」を用いるのが良さそうですね。
「Union Findアルゴリズム」、何か聞き覚えがあると思ったら、以前、取り組んだことがありました。以前、取り組んだのに肝心なときに使えないということは、知識として定着していないということだと思いますが、今回の失敗が成功のもとになれば、今回の挑戦は意味があるのだと思います(思いたいです)。

• クラスカルのアルゴリズム

nick.rb

# -*- coding: utf-8 -*-
n2g = { }               # ニックネームからグループ番号への対応付け
group_no = 0

open("nick.txt").each {|line|
  l, r = line.chomp.split('=')
  if n2g[l].nil? && n2g[r].nil? # 両辺のニックネームとも初出
    n2g[l] = group_no
    n2g[r] = group_no
    group_no += 1
  elsif n2g[l] && n2g[r] # <-- 追加(両辺のニックネームとも既出)
    old_group_no = n2g[r]
    n2g.each_key {|key|
      n2g[key] = n2g[l] if n2g[key] == old_group_no
    }
  elsif n2g[l]           # 左辺のニックネームが既出
    n2g[r] = n2g[l]
  elsif n2g[r]           # 右辺のニックネームが既出
    n2g[l] = n2g[r]
  end
}

g2n = Hash.new {|hash, key| hash[key] = [] } # グループ番号からニックネームへの対応付け
n2g.each {|key, val|
  g2n[val] << key
}
g2n.each {|key, val|
  val.sort!
}
ans = { }
g2n.each{|key, val|
  ans[val.first] = val
}
ans.keys.sort.each {|key|
  puts ans[key].join('=')
}