Minimum Spanning Tree
The minimum spanning tree: Kruskal's algorithm = sorting edges + DSU.
The problem: connect all n cities with roads of minimum total cost. The answer is always a tree of n-1 edges (a redundant edge in a cycle can be thrown away); it is called the minimum spanning tree (MST).
Kruskal's algorithm is a greedy that provably works:
1. Sort the edges by weight.
2. Go from cheap to expensive; take an edge if it connects DIFFERENT components.
3. "Are the components different" is checked by the DSU from the previous level — this is where it shines!
Complexity: O(m log m) for the sorting; the DSU is almost free.
Kruskal. Enter: 4 5, then the edges: 1 2 1, 2 3 2, 3 4 5, 1 3 2, 2 4 4
On the example: edges in increasing weight order are 1, 2, 2, 4, 5. Take 1-2 (weight 1), take 2-3 (weight 2), skip edge 1-3 (already in one component), take 2-4 (weight 4). Total: 1 + 2 + 4 = 7.
Why the greed is correct: the cheapest edge across any "cut" of the graph necessarily belongs to some MST (if not — add it; a more expensive edge across the same cut appears in the cycle; throw that one away — no worse). It is the same exchange argument from the greedy lesson.
There is also Prim's algorithm (grow the tree from a vertex, Dijkstra-style) — the same result, a different style.
Task: modify the program to print not only the weight but also the edges of the spanning tree itself.
Mark the lesson as completed and move on to the level's main topic — dynamic programming.