The challenge
Build a minimum spanning forest of an undirected weighted graph by choosing globally cheap edges while avoiding cycles.
List each undirected edge once. Use Union-Find to decide whether endpoints are already connected.
Example
The connected graph has minimum total weight 8. The B–F edge is accepted before A–B, which is then rejected as a cycle.
Use the walkthrough below to inspect the input and each state change.
See Kruskal, step by step
Follow the edges. Watch the state change.
Undirected · 6 vertices · 7 edgesA = 0, B = 1, …
CurrentVisited / acceptedUnvisitedLabels identify components or colors
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| A | B | C | D | E | F |
Step 01 / 9
Start with one component per vertex.
Sort all edges by weight. Accept an edge only when its endpoints are in different components.
edges.sort(key=weight)Forest
Total weight: 06 component(s)
View input edges
A — B (4) · A — F (1) · F — B (2) · B — C (1) · F — E (8) · C — D (3) · D — E (1)
Put it into code
The cheapest edge connecting different components is safe to accept.
Vertices are numbered 0 to V − 1. C++ uses C++17 or later.
# Undirected edges are listed once as (u, v, weight).
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
self.components = n
def find(self, u):
while u != self.parent[u]:
self.parent[u] = self.parent[self.parent[u]]
u = self.parent[u]
return u
def union(self, u, v):
a, b = self.find(u), self.find(v)
if a == b:
return False
if self.size[a] < self.size[b]:
a, b = b, a
self.parent[b] = a
self.size[a] += self.size[b]
self.components -= 1
return True
def kruskal(n, edges):
dsu = DSU(n)
forest, total = [], 0
for u, v, weight in sorted(edges, key=lambda e: e[2]):
if dsu.union(u, v):
forest.append((u, v, weight))
total += weight
return forest, total # V - components accepted edges.#include <numeric>
#include <utility>
#include <vector>
struct DSU {
std::vector<int> parent, size;
int components;
explicit DSU(int n) : parent(n), size(n, 1), components(n) {
std::iota(parent.begin(), parent.end(), 0);
}
int find(int u) {
while (u != parent[u]) {
parent[u] = parent[parent[u]];
u = parent[u];
}
return u;
}
bool unite(int u, int v) {
int a = find(u), b = find(v);
if (a == b) return false;
if (size[a] < size[b]) std::swap(a, b);
parent[b] = a;
size[a] += size[b];
--components;
return true;
}
};
#include <algorithm>
#include <tuple>
using ll = long long;
using Edge = std::tuple<int, int, ll>;
std::pair<std::vector<Edge>, ll> kruskal(int n, std::vector<Edge> edges) {
std::sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return std::get<2>(a) < std::get<2>(b);
});
DSU dsu(n);
std::vector<Edge> forest;
ll total = 0;
for (auto [u, v, weight] : edges) {
if (dsu.unite(u, v)) {
forest.push_back({u, v, weight});
total += weight;
}
}
return {forest, total};
}