Rubyで同値関係を求めるパズル

問題
xxxx=yyyy という形式のデータをたくさん受け取り、等しいもの同士をグルーピングするプログラムを書いてください。データは標準入力から与え、グルーピングした結果は { xxxx, yyyy } のように集合のような形式で標準出力に出すことにします。以下に入力と出力の組の例を示します。グループ同士の出力順は問いませんが、グループの中の各要素は適宜ソートしてください。
◆入力1

b=d
A=B
b=a
B=C
c=b
D=A

◆出力1

{ a, b, c, d }
{ A, B, C, D }

◆入力2

Alice=Alice
Robert=Bob
Liz=Beth
Lisa=Liza
Bess=Beth
Elizabeth=Lisa
Eliza=Liza
Bess=Elizabeth

◆出力2

{ Bob, Robert }
{ Alice }
{ Bess, Beth, Eliza, Elizabeth, Lisa, Liz, Liza }

◆入力3

少女=リズ
少年=ペタ
楽天家=ゲルト
老人=モーリッツ
ジム=ジムゾン
アル=商人
村長=ヴァルター
木こり=トーマス
旅人=ニコラス
ならず者=ディーター
少女=リーザ
行商人=アルビン
ジムゾン=神父
女将=宿屋の女主人
ヴァルター=ヴァル
商人=行商人
少年=ペーター
翁=モーリッツ
羊飼い=カタリナ
パン屋=オットー
青年=ヨアヒム
村娘=パメラ
農夫=ヤコブ
宿屋の女主人=レジーナ
リー=少女
ならず者=ディー
ペー太=ペタ

◆出力3

{ オットー, パン屋 }
{ パメラ, 村娘 }
{ モーリッツ, 翁, 老人 }
{ ならず者, ディー, ディーター }
{ リー, リーザ, リズ, 少女 }
{ ペーター, ペー太, ペタ, 少年 }
{ レジーナ, 宿屋の女主人, 女将 }
{ アル, アルビン, 行商人, 商人 }
{ トーマス, 木こり }
{ ニコラス, 旅人 }
{ ヤコブ, 農夫 }
{ ゲルト, 楽天家 }
{ カタリナ, 羊飼い }
{ ヨアヒム, 青年 }
{ ジム, ジムゾン, 神父 }
{ ヴァル, ヴァルター, 村長 }

※入力3のデータは、人狼BBSまとめサイトから借用しました。
http://wolfbbs.halfmoon.jp/?%C5%D0%BE%EC%BF%CD%CA%AA (現在はNot Found？)
解答

tree = Hash.new
while line = ARGF.gets
  line.chomp!
  next unless /([^=]+)=([^=]+)/ =~ line
  x, y = $1, $2
  x = tree[x] while tree[x]
  y = tree[y] while tree[y]
  tree[x] = y unless x == y
  tree[y] = nil;
end

equiv = Hash.new
tree.keys.each do |node|
  root = node
  root = tree[root] while tree[root]
  equiv[root] = [] unless equiv[root]
  equiv[root] << node
end

equiv.keys.sort.each do |root|
  puts "{ #{ equiv[root].sort.join(', ') } }"
end

はじめのwhileループでは、xxxx=yyyyの情報を見つけるごとに木構造を作っているハッシュtreeを更新します。treeの木構造は、tree[x]がxの「親を指す」という変則的なもの。xから始まる木とyから始まる木の「根」同士を比較して、違っていたら、片方を片方の根にぶら下げることで、2つの木を一本の木にまとめます。このwhileループが終わったとき、treeの中には木が集まった「森」ができています。
次のtree.keys.eachによるループでは、ハッシュequivを更新します。このハッシュequivは、森に生えている木の根をキーとして、その木のすべての節を集めた配列を値としています。
この方法は『The Art of Computer Programming Volume 1 日本語版』(Donald E. Knuth著, ISBN4-7561-4411-X, 2004年)のp.343に書かれている同値関係処理のためのアルゴリズムを参考にしています。通常は木構造というと「親から子の節を指す」ことが多いのですが、これは子が親の節を指すことが重要な意味を持つ例だそうです。
実行結果です。

C:\work> type names
Alice=Alice
Robert=Bob
Liz=Beth
Lisa=Liza
Bess=Beth
Elizabeth=Lisa
Eliza=Liza
Bess=Elizabeth

C:\work> ruby equiv.rb < names
{ Alice }
{ Bob, Robert }
{ Bess, Beth, Eliza, Elizabeth, Lisa, Liz, Liza }

要するに、「木構造」のルートはその同値類の代表元になっているのですね。
今回のエントリは結城浩の『Perlクイズ』2004-06-18 No.0087をベースにしています。