用途
最小全域木を求める.
計算量
$ O(|E|\log|E|) $
Depends
使い方
宣言
resに最小全域木のUndirectedGraphを得る.
実装
1
2
3
4
5
6
7
8
9
10
11
| 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;
}
|