Minimum Spanning Tree
Connect a weighted graph as cheaply as possible, usually with Kruskal and DSU as the contest default.
Minimum Spanning Tree
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Minimum spanning tree is the weighted-graph tool for ``connect everything as cheaply as possible.'' In contest code, Kruskal plus DSU is usually the shortest reliable route, and it also exposes the structural properties that later MST reductions depend on.
When to Use It
Use MST ideas when:
the graph is undirected and weighted,
the goal is to connect all vertices with minimum total cost,
the statement hides a connectivity threshold or bottleneck argument.
Core Idea
A spanning tree uses exactly \(n-1\) edges and connects every vertex. Kruskal's algorithm sorts edges by weight and adds an edge exactly when it joins two different DSU components.
Key Insight
The reason Kruskal is safe is the cut property: for any cut of the graph, the lightest edge crossing that cut belongs to some MST. Kruskal keeps applying this fact globally by always taking the cheapest edge that does not create a cycle.
Worked Problem
Problem.
There are \(n\) outposts and weighted undirected roads. Build roads so every outpost can reach every other and the total construction cost is minimum.
Algorithm outline.
Sort all roads by weight.
Scan from cheapest to most expensive.
If a road joins two different DSU components, take it.
Stop after taking \(n-1\) roads.
Why this greedy step is correct.
At the moment Kruskal considers edge \(e\), its endpoints lie in two different components of the partial forest. Those components define a cut, and \(e\) is the lightest edge crossing that cut that has not already been skipped for creating cycles. By the cut property, some MST can include it.
Example Problem Pattern
Another common use is a threshold problem:
What is the minimum value \(T\) such that the graph becomes connected using only edges of weight at most \(T\)?
The answer is the maximum edge weight used by the MST. This is a bottleneck interpretation of the same structure.
Correctness Intuition
Every time Kruskal adds an edge, it is forcing one safe edge into the final tree. Repeating that exchange argument eventually yields a full spanning tree, and no cheaper tree can exist because each chosen edge was safe at the moment it was taken.
Complexity Analysis
sorting edges: \(O(m \log m)\),
DSU operations: near-linear,
total: \(O(m \log m)\).
Implementation
The reference code returns both the total MST weight and the chosen edge list. That makes it easy to continue with tree queries or bottleneck analysis afterward.
Common Pitfalls
Using MST language on a directed graph.
Forgetting to detect the disconnected case.
Confusing MST with single-source shortest paths.
Using 32-bit sums when edge weights are large.
Variants / Extensions
Prim's algorithm for dense graphs or adjacency-matrix settings.
Maximum spanning tree.
Second-best MST and replacement-edge queries.
Practice Problems
Standard minimum spanning tree construction.
Threshold-to-connect problems.
Build the MST first, then answer queries on the resulting tree.
References
Code
Contest-ready reference implementation for the idea explained above.
struct Edge {
int u;
int v;
long long w;
};
struct Dsu {
vector<int> parent;
vector<int> size;
explicit Dsu(int n) : parent(n), size(n, 1) {
iota(parent.begin(), parent.end(), 0);
}
int find(int v) {
if (parent[v] == v) return v;
return parent[v] = find(parent[v]);
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (size[a] < size[b]) swap(a, b);
parent[b] = a;
size[a] += size[b];
return true;
}
};
pair<long long, vector<Edge>> kruskal_mst(int n, vector<Edge> edges) {
sort(edges.begin(), edges.end(), [](const Edge& lhs, const Edge& rhs) {
return lhs.w < rhs.w;
});
Dsu dsu(n);
long long total = 0;
vector<Edge> chosen;
for (const Edge& e : edges) {
if (dsu.unite(e.u, e.v)) {
total += e.w;
chosen.push_back(e);
}
}
if ((int)chosen.size() != n - 1) {
return {-1, {}};
}
return {total, chosen};
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.