クラスカル法
無向連結グラフの最小全域木を求めるアルゴリズム
O(E log E)
辺のコストを安い方から閉路を作らないように追加していく
この閉路の判定はUnionFindを使うことでほぼ定数時間
辺をコストによってソートするところでO(E log E)
ソート済みもしくは線形時間ソートできるならO(E)
最小全域木（クラスカル法とUnionFind） - アルゴリズム講習会
クラスカル法 - Wikipedia