206(23): デフォルトの名無しさん [] 2024/02/02(金) 06:41:15.23 ID:CC6U77IS(1) AAS
お題
入力データをグループ分けして出力せよ

入力データの、= の左右は同じグループである。
出力する順番は、入力データの出現順とする

UnionFind を使えば良いかも

入力データ
["a1=a2", "b1=b2", "b3=b2", "c1=c2", "e1=e2",
"a3=a4", "c3=c4", "e1=e3", "a2=a4", "c3=c1",
"b3=a4", "c2=d1", "a4=a5", "d2=c1", "b4=b3", "d3=c3"]

出力
[["a1", "a2", "b1", "b2", "b3", "a3", "a4", "a5", "b4"],
["c1", "c2", "c3", "c4", "d1", "d2", "d3"],
["e1", "e2", "e3"]]

Ruby で、UnionFind を自作してみた。
下はユニットテストです

外部ﾘﾝｸ:paiza.io
外部ﾘﾝｸ:paiza.io

223(2): 221 [sage] 2024/02/05(月) 20:08:21.07 ID:tt/WRhkt(1/2) AAS
>>206 ruby
外部ﾘﾝｸ:ideone.com
・>>221から若干のアレンジ
・SortedSet単位でのみいじるようにした
f = -> a {
g = -> a {a.combination(2) {|x, y| break g.(a.tap {x.merge y; a.delete y}) if x.intersect? y}}
h = a.map {|s| s.split('=')}.flatten.uniq.map.with_index.to_h
a = a.map {|s| s.split('=').map {|k| h[k]}.to_set SortedSet}
g.(a).map {|set| set.map &h.invert.method(:[])}
}