Connect every node at minimum total cost. Kruskal's sorts all edges cheapest-first and greedily adds each one, unless it would form a cycle. Union-Find is the cycle referee.
Sort edges by weight ascending. Walk them cheapest-first: if an edge joins two different components, take it (union them). If both ends are already connected, it'd make a cycle, skip it.
find(x) returns x's component rootV-1 edgesint parent[MAXN], rnk[MAXN];
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false; // same set → cycle
if (rnk[a] < rnk[b]) swap(a, b);
parent[b] = a;
if (rnk[a] == rnk[b]) rnk[a]++;
return true;
}
int kruskal(int n, vector<array<int,3>>& edges) {
for (int i = 0; i < n; i++) parent[i] = i, rnk[i] = 0;
sort(edges.begin(), edges.end(), // by weight ascending
[](auto& a, auto& b){ return a[2] < b[2]; });
int cost = 0, used = 0;
for (auto& [w, u, v] : edges) {
if (unite(u, v)) { // joins two components
cost += w; used++;
if (used == n - 1) break; // MST complete
}
}
return cost;
}Dominated by sorting the edges. Union-Find ops are near-constant.
Parent and rank arrays for the disjoint-set structure.
A spanning tree of V nodes has exactly V-1 edges.
find/unite effectively O(α(n)), basically constant.