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