And that's already working code for
Kruskal algorithm for finding MST (obviously using
Disjoint Set Union)
struct Edge {
int u, v, weight;
};
bool comp(Edge e, Edge f) {
return e.weight < f.weight;
}
vector<Edge> edges;
int n, m, rep[n];
int Find(int v) {
if (rep[v] == v) return v;
return rep[v] = Find(rep[v]);
}
void Union(int u, int v) {
rep[Find(u)] = Find(v);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) rep[i] = i;
for (int i = 1; i <= m; i++) {
int u, v, weight;
cin >> u >> v >> weight;
edges.push_back({u, v, weight});
}
sort(edges.begin(), edges.end(), comp);
for (Edge e : edges)
if (Find(e.u) != Find(e.v))
Union(e.u, e.v);
}
Enjoy!