content/graph/kruskal.cpp


1
2
3
4
5
6
7
8
9
10
11

ll kruskal(int n, vector<Edge> edges, vector<Edge> &mst) {
	ranges::sort(edges, less{});
	ll cost = 0;
	UnionFind uf(n); // union find @\sourceref{datastructures/unionFind.cpp}@
	for (Edge &e: edges) {
		if (uf.link(e.from, e.to)) {
			mst.push_back(e);
			cost += e.cost;
	}}
	return cost;
}