MST Practice Questions
Eight problems covering every algorithm and pattern in the chapter. The easy problems test pure union-find; the medium ones require recognizing the MST framing; the hard ones combine techniques.
Before reading any solution, ask:
- Is this a “connect all nodes at minimum cost” problem? → MST (Kruskal or Prim).
- Does it ask about connectivity or cycles? → Union-Find.
- Is the graph implicitly complete (all pairs connected)? → Prim’s dense O(V²) variant.
- Does it involve two types of edges or constraints? → Dual union-find or virtual node trick.
The pattern is almost always visible once you squint at the problem the right way.
Easy
| Problem | Pattern | Status |
|---|---|---|
| Min Cost to Connect All Points | Prim’s dense O(V²) on implicit complete graph | Available |
| Redundant Connection | Union-Find — detect the first cycle-forming edge | Available |
Medium
| Problem | Pattern | Status |
|---|---|---|
| Number of Operations to Make Network Connected | Union-Find — count components and spare cables | Available |
| Remove Max Number of Edges to Keep Graph Fully Traversable | Dual Union-Find (Alice + Bob) | Available |
| Most Stones Removed with Same Row or Column | Union-Find on row/column indices | Available |
| Accounts Merge | Union-Find on email strings | Available |
Hard
| Problem | Pattern | Status |
|---|---|---|
| Find Critical and Pseudo-Critical Edges in MST | Kruskal with force/skip per edge | Available |
| Swim in Rising Water | Binary search + BFS, or min-max path (MST-adjacent) | Available |
More Practice (Coming Soon)
| Problem | Pattern | Status |
|---|---|---|
| Optimize Water Distribution in a Village | Virtual node + Kruskal | Coming Soon |
| Minimum Spanning Tree (generic) | Kruskal / Prim | Coming Soon |
| Connecting Cities With Minimum Cost | Standard Kruskal | Coming Soon |
| Min Cost to Repair Edges | Modified Kruskal | Coming Soon |
| Minimum Cost to Connect Two Groups | DP on subsets + MST | Coming Soon |
| Smallest String With Swaps | Union-Find on index pairs | Coming Soon |
| Satisfiability of Equality Equations | Union-Find on variables | Coming Soon |
| Largest Component Size by Common Factor | Union-Find with factor grouping | Coming Soon |