クラスカル法

前提

辺がすべてわかっている

辺の配列がソート済みである

手順

code:ruby

uf = UnionFind.new(N)

total_cost = 0

# edgeは頂点u,頂点v,頂点間のcostを持つ

edges.each do |cost, u, v|

# 辺を追加しても閉路（サイクル）ができないなら、その辺を採用する

if !uf.connected?(u,v)

uf.unite(u, v)

total_cost += cost # 採用した辺のコストを足す

end

end

参考

例題