Graphs -> Minimum Spanning Tree

Use cut and cycle properties to build minimum spanning forests with Kruskal or Prim.

• Topic slug: graphs/mst
• Tutorial page: Open tutorial
• Ladder page: Open ladder
• Repo problems currently tagged here: 1
• Repo companion pages: 0
• Curated external problems: 6

Microtopics

• kruskal
• prim
• dsu
• cut-property
• cycle-property
• minimum-spanning-forest

Learning Sources

Source	Type
Princeton MST	Course
cp-algorithms Kruskal	Reference
cp-algorithms Prim	Reference

Practice Sources

Source	Type
CSES Problem Set	Practice
USACO contest archive	Practice

Curated External Problems

Core

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Minimum Spanning Tree	Kattis	Easy	-	-	-	Kruskal; Classic	A standard trusted MST practice problem.

Coordinate MST

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Built?	AtCoder	Medium	Geometry	Sorting By Coordinate; Candidate Edge Pruning; Kruskal	DSU; Sorting; Greedy MST	Coordinate Graph; Sparse Edges	A classic geometry-to-graph reduction before running Kruskal.

Kruskal

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Minimum Spanning Tree	AOJ	Medium	DSU	Edge Sorting; Union-Find; Weight Accumulation	Sorting; Tree Connectivity	MST Sum; Weighted Graph; Kruskal; Weighted Undirected	The canonical official MST verification problem from AOJ.
Road Reparation	CSES	Medium	DSU	Edge Sorting; DSU Merges; Component Counting	Sorting; Greedy Choice	Minimum Spanning Tree; Connectivity	The standard MST warm-up with a clean connectivity check.

MST Variants

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Minimum spanning tree for each edge	Codeforces	Hard	-	Kruskal Base Tree; Max-Edge Queries On Path; Replacement Reasoning	MST; LCA Or HLD; Tree Path Maximum	Replacement Edge; MST Variants; Binary Lifting	A strong follow-up to plain MST that asks for edge-wise replacement analysis.

MST Verification

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Minimum Spanning Tree	Library Checker	Medium	-	Kruskal Template; Edge Index Handling; DSU	MST Basics; DSU; Weighted Edges	Sparse Graph; DSU; Verify	A clean judge problem for checking a production-ready MST implementation.

Repo Problems

Code	Title	Fit	Difficulty	Pattern	Note	Solution
ROADREPARATION	Road Reparation	primary	medium	kruskal mst; connectivity check; cut property greedy	Note	Code

Regeneration

python3 scripts/generate_problem_catalog.py