最小全域木 MST (minimum spanning tree)

解法

  • Kruskal法を使う
    • 辺を列挙し、コストの軽いものから見ていって非連結じゃない頂点をつなぐなら採用する
  • 同じグループ判定にUnion Findを使う
  • エッジコストの小さい順に取り出すためにPriority Queueを使う
    • ソート済みのvectorでもよい

小さい順に取り出すpriority_queue

// コストの小さい順に取り出す設定
priority_queue<Edge, vector<Edge>, greater<Edge> > que;

他にMSTを使う問題

類題