Chapter 8.1: Minimum Spanning Tree

📝 Before You Continue: This chapter requires Chapter 5.1–5.3 (graphs, BFS/DFS, Union-Find/DSU). You must understand DSU's find and union operations before reading Kruskal's algorithm.

A minimum spanning tree (MST) of a weighted undirected graph is a subset of edges that:

1. Connects all N vertices (spanning)
2. Forms no cycles (tree)
3. Has the minimum possible total edge weight

MSTs appear in USACO Gold problems disguised as: "build the cheapest network," "find the minimum cost to connect all nodes," or problems where you need to think about which edges are necessary.

Learning objectives:

• Understand what a spanning tree is and why the MST is useful
• Implement Kruskal's algorithm using DSU in O(E log E)
• Implement Prim's algorithm using a priority queue in O(E log V)
• Recognize MST problems in USACO and apply the cut/cycle properties

8.1.0 What Is a Spanning Tree?

Given a connected graph with N vertices and E edges, a spanning tree is any subset of edges that:

• Connects all N vertices
• Uses exactly N−1 edges
• Contains no cycle

A graph can have many spanning trees. The minimum spanning tree is the one whose edges sum to the smallest total weight.

Graph:                    One spanning tree:         MST:
  1                         1                          1
 / \                       / \                        / \
2   3   weights:          2   3                      2   3
|\ /|   1-2: 4            |                          |
| X |   1-3: 2            4                          4
|/ \|   2-3: 5      total=4+2+3=9            total=4+2+1=7 ← minimum
4   5   2-4: 3
        3-4: 1
        4-5: 6

💡 Why N−1 edges? A tree on N nodes always has exactly N−1 edges. Fewer edges means disconnected; more edges means a cycle.

8.1.1 The Cut Property and Cycle Property

Two fundamental facts that make MST algorithms work:

Cut Property: For any cut of the graph (partition of vertices into two sets S and V−S), the minimum-weight edge crossing the cut must be in every MST.

Cycle Property: For any cycle in the graph, the maximum-weight edge in that cycle cannot be in any MST (unless there are ties).

These properties justify both Kruskal's and Prim's algorithms.

8.1.2 Kruskal's Algorithm

Core idea: Sort all edges by weight. Greedily add the cheapest edge that doesn't create a cycle. Use DSU to detect cycles in O(α(N)) ≈ O(1).

Algorithm:

1. Sort all edges by weight (ascending)
2. Initialize DSU with N components (each vertex is its own component)
3. For each edge (u, v, w) in sorted order:
   • If find(u) ≠ find(v): add edge to MST, call union(u, v)
   • Else: skip (would create a cycle)
4. Stop when MST has N−1 edges

#include <bits/stdc++.h>
using namespace std;

// ── DSU (Union-Find) ──────────────────────────────────
struct DSU {
    vector<int> parent, rank_;
    int components;

    DSU(int n) : parent(n), rank_(n, 0), components(n) {
        iota(parent.begin(), parent.end(), 0); // parent[i] = i
    }

    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);  // path compression
        return parent[x];
    }

    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;           // already in same component
        if (rank_[x] < rank_[y]) swap(x, y);
        parent[y] = x;                      // attach smaller rank to larger
        if (rank_[x] == rank_[y]) rank_[x]++;
        components--;
        return true;
    }

    bool connected(int x, int y) { return find(x) == find(y); }
};

// ── Kruskal's MST ────────────────────────────────────
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;  // n vertices, m edges

    // edges[i] = {weight, u, v}
    vector<tuple<int,int,int>> edges(m);
    for (auto& [w, u, v] : edges) {
        cin >> u >> v >> w;
        u--; v--;  // 0-indexed
    }

    sort(edges.begin(), edges.end());  // sort by weight (first element)

    DSU dsu(n);
    long long mst_weight = 0;
    int edges_added = 0;
    vector<pair<int,int>> mst_edges;

    for (auto& [w, u, v] : edges) {
        if (dsu.unite(u, v)) {      // adds edge only if no cycle
            mst_weight += w;
            mst_edges.push_back({u, v});
            edges_added++;
            if (edges_added == n - 1) break;  // MST complete
        }
    }

    if (edges_added < n - 1) {
        cout << "Graph is not connected — no MST exists\n";
    } else {
        cout << "MST weight: " << mst_weight << "\n";
    }

    return 0;
}

Complexity: O(E log E) for sorting + O(E · α(N)) for DSU operations ≈ O(E log E).

Tracing Kruskal's on an Example

Vertices: 4 (0, 1, 2, 3)
Edges (sorted): (0,1,1), (1,2,2), (2,3,3), (0,2,5), (1,3,6)

Step 1: edge (0,1,w=1) → find(0)=0 ≠ find(1)=1 → ADD  DSU: {0,1},{2},{3}
Step 2: edge (1,2,w=2) → find(1)=0 ≠ find(2)=2 → ADD  DSU: {0,1,2},{3}
Step 3: edge (2,3,w=3) → find(2)=0 ≠ find(3)=3 → ADD  DSU: {0,1,2,3}
        edges_added = 3 = n-1 → DONE

MST weight = 1 + 2 + 3 = 6

8.1.3 Prim's Algorithm

Core idea: Grow the MST from a starting vertex. At each step, add the minimum-weight edge that connects a vertex inside the MST to a vertex outside. Use a min-heap (priority queue) to always pick the cheapest edge efficiently.

When to prefer Prim's over Kruskal's: Dense graphs (E ≈ V²), since Prim with adjacency list + heap runs in O(E log V), while Kruskal sorts E edges in O(E log E). For dense graphs E log V < E log E, but in practice both work for competitive programming constraints.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    // Adjacency list: adj[u] = list of {weight, neighbor}
    vector<vector<pair<int,int>>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});  // undirected
    }

    // Prim's with min-heap
    vector<bool> in_mst(n, false);
    long long mst_weight = 0;
    int edges_added = 0;

    // min-heap: {edge_weight, vertex}
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, 0});  // start from vertex 0, cost 0

    while (!pq.empty() && edges_added < n) {
        auto [w, u] = pq.top(); pq.pop();

        if (in_mst[u]) continue;  // already included, skip (lazy deletion)
        in_mst[u] = true;
        mst_weight += w;
        edges_added++;

        for (auto [edge_w, v] : adj[u]) {
            if (!in_mst[v]) {
                pq.push({edge_w, v});  // candidate edge to expand MST
            }
        }
    }

    if (edges_added < n) {
        cout << "Graph is not connected\n";
    } else {
        cout << "MST weight: " << mst_weight << "\n";
    }

    return 0;
}

Complexity: O(E log V) with binary heap.

8.1.4 MST Properties for Problem Solving

Beyond computing the MST itself, several properties are useful in USACO:

Property 1: Uniqueness

If all edge weights are distinct, the MST is unique. If there are ties, multiple MSTs may exist with the same total weight.

Property 2: Bottleneck Spanning Tree

The MST minimizes the maximum edge weight on any path between two vertices. This means: the MST path between u and v uses the smallest possible "bottleneck" edge.

💡 USACO application: "What is the minimum possible maximum edge on a path from u to v?" → Answer is the maximum edge on the MST path from u to v.

Property 3: MST as Greedy Framework

Many USACO Gold problems reduce to Kruskal's algorithm with a twist:

• Sort "connections" by some cost
• Greedily merge groups as long as the merge is valid
• DSU tracks which groups are already connected

Kruskal's Algorithm on Non-Standard "Edges"

A classic USACO pattern: edges aren't given explicitly — you must figure out what to sort and what "merging" means.

Example pattern (USACO 2016 February Gold — Fencing the Cows):

• Cows are in groups; connecting two cows has a cost
• Goal: connect all cows with minimum total cost
• Solution: model as graph, run Kruskal's

8.1.5 Kruskal's Reconstruction Tree

The Kruskal reconstruction tree (also called Kruskal tree) is a powerful structure built during Kruskal's algorithm that encodes the "merge history" of connected components.

Construction: When Kruskal's algorithm merges components containing u and v via an edge of weight w:

• Create a new node x with value w
• Make the roots of u's component and v's component children of x
• Replace both components with x as their new root

The resulting tree has:

• N leaf nodes (original vertices)
• N-1 internal nodes (one per MST edge, with value = edge weight)
• 2N-1 total nodes

Example MST edges (sorted): (0,1,w=1), (1,2,w=2), (2,3,w=3)

After (0,1,w=1):   Node 4 (w=1)
                    / \
                   0   1

After (1,2,w=2):   Node 5 (w=2)
                    / \
              Node4    2
              (w=1)
               / \
              0   1

After (2,3,w=3):   Node 6 (w=3)
                    / \
                 Node5   3
                 (w=2)
                  / \
               Node4  2
               (w=1)
                / \
               0   1

Key Property: LCA = Bottleneck Edge

The value of LCA(u, v) in the Kruskal tree = the weight of the maximum edge on the MST path from u to v = the minimum possible bottleneck between u and v.

This means:

• Query "minimum bottleneck between u and v" → find LCA in Kruskal tree
• Query "what is the minimum edge weight such that u and v are connected?" → same as above

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent, rank_, root;  // root[i] = Kruskal tree node that is root of component i
    DSU(int n) : parent(n), rank_(n, 0), root(n) {
        iota(parent.begin(), parent.end(), 0);
        iota(root.begin(), root.end(), 0);
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    // Returns the new Kruskal tree node created by this merge
    int unite(int x, int y, int new_node) {
        x = find(x); y = find(y);
        if (x == y) return -1;
        if (rank_[x] < rank_[y]) swap(x, y);
        parent[y] = x;
        if (rank_[x] == rank_[y]) rank_[x]++;
        root[x] = new_node;   // new Kruskal tree node is root of merged component
        return new_node;
    }
    int get_root(int x) { return root[find(x)]; }
};

// Build Kruskal reconstruction tree
// Returns: kruskal_tree adjacency list and node values
// Leaves 0..n-1 are original vertices; nodes n..2n-2 are internal (MST edges)
void build_kruskal_tree(
        int n,
        vector<tuple<int,int,int>>& edges,   // {weight, u, v} — must be sorted
        vector<vector<int>>& ktree,          // ktree[node] = children in Kruskal tree
        vector<int>& node_val                // node_val[node] = edge weight (internal) or 0 (leaf)
) {
    ktree.assign(2 * n, {});
    node_val.assign(2 * n, 0);

    DSU dsu(n);
    int next_node = n;  // next internal node ID

    for (auto [w, u, v] : edges) {
        int ru = dsu.find(u), rv = dsu.find(v);
        if (ru == rv) continue;  // same component, skip

        // Create new internal node
        int x = next_node++;
        node_val[x] = w;

        // Add children: roots of u's and v's Kruskal tree
        ktree[x].push_back(dsu.get_root(u));
        ktree[x].push_back(dsu.get_root(v));

        dsu.unite(u, v, x);
    }
}

// After building, use binary lifting LCA on ktree to answer bottleneck queries
// lca(u, v) in ktree gives the bottleneck edge weight between u and v in MST

USACO Gold Applications

Pattern: "For each query (u, v, k), count vertices reachable from u using only edges ≤ k"

In the Kruskal tree, the subtree of the LCA at threshold k contains exactly the vertices reachable from u when only edges of weight ≤ node_val[LCA] are available.

// Query: how many vertices are in the same component as u
// when only edges with weight <= threshold are used?
// → Find the deepest ancestor x of u in Kruskal tree with node_val[x] <= threshold
// → Answer = sz[x] (subtree size, which counts leaves = original vertices)

💡 Why this works: The Kruskal tree records exactly the order in which edges were merged. The subtree of an internal node x contains all vertices that were in the same component when edge of weight node_val[x] was added.

8.1.6 USACO Gold Problem Patterns

Pattern 1: Direct MST

"Connect all N nodes with minimum total connection cost."

Apply Kruskal's or Prim's directly.

Pattern 2: Sort + DSU (Kruskal-style greedy)

"Process events/pairs in some order; merge groups; query connectivity."

This is Kruskal's without explicitly calling it MST. The key insight: sort the pairs by some criterion, then use DSU to merge.

// Template: Kruskal-style greedy
sort(events.begin(), events.end(), comparator);
DSU dsu(n);
for (auto& event : events) {
    if (dsu.unite(event.u, event.v)) {
        // process the merge
    }
}

Pattern 3: MST + Additional Query

"Find MST, then answer queries about paths in the MST."

Build the MST, then build a tree from MST edges, then answer path queries (often combined with Euler tour from Ch.8.4).

💡 思路陷阱（Pitfall Patterns）

陷阱 1：把"最小瓶颈路"误当"最短路"

错误判断： "求 u 到 v 路径上最大边权的最小值，用 Dijkstra 最短路" 实际情况： 最短路最小化边权之和；最小瓶颈路最小化路径上的最大边 — 这是 MST 问题

图：u→A(w=1), u→B(w=5), A→v(w=10), B→v(w=6)
Dijkstra 最短路(u→v): u→A→v, 总权=11, 最大边=10
MST 瓶颈路(u→v):     u→B→v, 总权=11, 最大边=6  ← 最小瓶颈

关键：最小瓶颈路 = MST 上 u→v 的路径（Cut Property 保证）

识别信号： 题目要求"最小化路径上的最大/最重边" → MST + 树上路径，不是 Dijkstra

陷阱 2：贪心合并时忘记"Kruskal 视角"

错误判断： "按某种顺序处理操作，感觉像贪心，写个模拟" 实际情况： 操作可以排序 + 用 DSU 合并 → 本质是 Kruskal 的变体

典型题：N 个集合，每次可以合并代价最小的两个集合（权重 = 两集合大小之积）
错误：模拟优先队列，每次弹出最小的两个合并 → 复杂度 O(N² log N)
正确：认识到"按代价排序 + DSU 合并"就是 Kruskal-style greedy → O(N log N)

识别信号： "处理 N 个对象，按某种代价合并，最终连通" → 先想 Kruskal 框架

⚠️ Common Mistakes

1. Forgetting to check connectivity: Not all graphs are connected. After Kruskal's, verify edges_added == n - 1. After Prim's, verify edges_added == n.

2. Wrong DSU (no path compression or union by rank): Naive DSU without optimization gives O(N) per operation, making Kruskal O(E·N) instead of O(E log E).

3. Off-by-one in edge count: MST has N−1 edges. If you stop at N edges, you've added one too many.

4. Applying Kruskal's to directed graphs: Both algorithms assume undirected edges. For directed graphs, use a different approach (minimum arborescence / Chu-Liu/Edmonds' algorithm — not tested in USACO Gold).

5. Integer overflow: If edge weights can be up to 10⁹ and N = 10⁵, the MST weight can reach ~10¹⁴. Use long long.

📋 Chapter Summary

📌 Key Takeaways

❓ FAQ

Q: When should I use Kruskal's vs Prim's? A: In competitive programming, Kruskal's with DSU is almost always preferred — it's simpler to implement and works well for sparse graphs (typical in USACO). Use Prim's for very dense graphs where E ≈ V².

Q: Does the MST change if I add a constant to all edge weights? A: No — adding a constant to all edges doesn't change which edges are in the MST (just the total weight).

Q: Can a graph have multiple MSTs? A: Yes, if some edge weights are equal. But the MST weight (total) is always unique.

Q: What if the graph is disconnected? A: There is no spanning tree (you can't connect all vertices). Instead, you compute a minimum spanning forest — one MST per connected component.

Q: My Kruskal's gives wrong answer on the USACO judge — what's wrong? A: Check: (1) Are you using 1-indexed or 0-indexed vertices consistently? (2) Is DSU's path compression correct? (3) Are you using long long for the total weight?

🔗 Connections to Later Chapters

• Ch.8.3 (Tree DP): After building the MST, it becomes a tree. You can run tree DP on the MST to answer path queries.
• Ch.8.4 (Euler Tour): Euler tour lets you answer range queries on the MST tree structure.
• Ch.5.3 (DSU): Kruskal's heavily uses DSU. Make sure you have Ch.5.3's path-compressed DSU ready as a template.

🏋️ Practice Problems

🟢 Easy

8.1-E1. Classic MST Given N cities and M roads with weights, find the minimum total weight to connect all cities. (Standard Kruskal's — warm-up)

#include <bits/stdc++.h>
using namespace std;
// ... (use Kruskal's template from 8.1.2)

8.1-E2. Connected? Given N nodes and M edges, determine if the graph is connected. If yes, output the MST weight. If no, output the number of connected components.

🟡 Medium

8.1-M1. Minimum Bottleneck Path (USACO-style) Given N nodes, M edges with weights, and Q queries (u, v): for each query, find the minimum possible maximum edge weight on any path from u to v.

8.1-M2. Kruskal-Style Greedy (USACO 2016 February Gold — Fencing the Cows) N cows, each in a pasture. Moving a cow between pastures i and j costs |i - j|. Connect all pastures into one group with minimum total cost.

🔴 Hard

8.1-H1. Dynamic Connectivity (Advanced) Given N nodes, process Q operations: "add edge (u,v,w)" or "query: what is the MST weight of all edges added so far?"

🏆 Challenge

8.1-C1. Steiner Tree (Approximation) Given a graph and a set S of "required" vertices, find the minimum-weight subtree that connects all vertices in S (the Steiner tree problem). For |S| ≤ 15, solve exactly using bitmask DP.