用途
最小全域木を求める.
計算量
Depends
使い方
宣言
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;}