プログラミングコンテストチャレンジブック演習「クラスカル法」

今回のお題はこちら

辺をコストの低い順に並べて、辺の始点と終点が同じ木に属していなければ辺を取り入れるというアルゴリズム。これは簡単ですな。

require 'union_find_tree'

V = 10 #input
E = 10 #input
$edges = Array.new(E, Hash.new) #input 辺の始点、終点、コスト

$edges.sort{|a, b| a["cost"] <=> b["cost"]}
union = UnionFindTree.new(V)
totalCost = 0
for i in 0..(E - 1)
  edge = $edges[i]
  unless union.same(edge["start"], edge["end"])
    union.unite(edge["start"], edge["end"])
    totalCost += edge["cost"]
  end
end
puts totalCost