Kruskal

romophic-library

用途

最小全域木を求める.

計算量

$ O(|E|\log|E|) $

Depends

UndirectedGraph
UnionFind

使い方

宣言

auto res = kruskal(g);

resに最小全域木のUndirectedGraphを得る.

実装

UndirectedGraph kruskal(UndirectedGraph &_g) {
  UnionFind uf(_g.n);
  UndirectedGraph res(_g.n);
  sort(_g.g.begin(), _g.g.end(), [](auto &l, auto &r) { return l.cost < r.cost; });
  for (auto &[u, v, cost] : _g.g) {
    if (uf.merge(u, v)) {
      res.add(u,v,cost);
    }
  }
  return res;
}