- Quiz
- AC
解法
- Kruskal法を使う
- 辺を列挙し、コストの軽いものから見ていって非連結じゃない頂点をつなぐなら採用する
- 同じグループ判定にUnion Findを使う
- エッジコストの小さい順に取り出すためにPriority Queueを使う
- ソート済みのvectorでもよい
小さい順に取り出すpriority_queue
// コストの小さい順に取り出す設定
priority_queue<Edge, vector<Edge>, greater<Edge> > que;
他にMSTを使う問題
- D - Built?
- 要素
- クラスカル O(E logE) (Eは辺数)
- UnionFind
- 点(x, y)の各ソート
- 必要な辺だけを張ることで辺数をO(N)に抑える
- Building a Space Station
類題
- L - グラデーション / Gradation
- L-都市計画
- ✅https://atcoder.jp/contests/past202104-open/submissions/24593696
- 点じゃなく円なので包含関係などが出てきて実装重い
- 点は半径0の円と考えると点と円を同一視できる(上記実装では未使用)