Kruskal

1
auto res = kruskal(g);

1
UndirectedGraph kruskal(UndirectedGraph &_g) {
2
  UnionFind uf(_g.n);
3
  UndirectedGraph res(_g.n);
4
  sort(_g.g.begin(), _g.g.end(), [](auto &l, auto &r) { return l.cost < r.cost; });
5
  for (auto &[u, v, cost] : _g.g) {
6
    if (uf.merge(u, v)) {
7
      res.add(u,v,cost);
8
    }
9
  }
10
  return res;
11
}