Kruskal Algorithm is based on Union-Find - quite intuitive.
#include <vector> #include <iostream> #include <queue> #include <unordered_map> #include <unordered_set> using namespace std; struct Edge { Edge() :s(0), t(0), d(0) {} Edge(unsigned rs, unsigned rt, unsigned rd) : s(rs), t(rt), d(rd) {} unsigned s; unsigned t; unsigned d; bool operator()(const Edge &e1, const Edge &e2) { if (e1.d != e2.d) return e1.d > e2.d; return (e1.s + e1.d + e1.t) > (e2.s + e2.d + e2.t); } }; // Union-Set unordered_map<unsigned, unsigned> pm; // smaller as parent unsigned get_union_id(unsigned id) { if (pm.find(id) == pm.end()) { pm[id] = id; return id; } unsigned ret = id; while(ret != pm[ret]) ret = pm[ret]; return ret; } void union_2id(unsigned id0, unsigned id1) { unsigned p0 = get_union_id(id0); unsigned p1 = get_union_id(id1); if(p0 < p1) pm[p1] = id0; else if(p0 > p1) pm[p0] = id1; } ////////////////////////////////////// int main() { long n, m; cin >> n >> m; priority_queue<Edge, vector<Edge>, Edge> q, qs; // from -> to -> length unordered_map<unsigned, unordered_map<unsigned, unsigned>> g; for (int i = 0; i < m; i++) { unsigned a, b, d; cin >> a >> b >> d; q.push(Edge(min(a,b), max(a,b), d)); g[a][b] = g[b][a] = d; } unsigned long long ret = 0; // Step 1 unsigned s; cin >> s; for (auto &kv : g[s]) { unsigned a = s; unsigned b = kv.first; qs.push(Edge(min(a, b), max(a, b), kv.second)); } // pick first const Edge &first = qs.top(); ret += first.d; union_2id(first.s, first.t); while (!q.empty()) { Edge picked = q.top(); q.pop(); if (get_union_id(picked.s) == get_union_id(picked.t)) continue; union_2id(picked.s, picked.t); ret += picked.d; } cout << ret << endl; return 0; }