Skip to content
CCC Python Course

Minimum spanning tree: Kruskal plus DSU

Stage
6
Module
M6.3
Lessons
1

In this module

  • Recognize when a minimum spanning tree solves a connectivity or infrastructure problem.
  • Implement Kruskal's algorithm sorting edges by weight.
  • Use a disjoint-set union (DSU) data structure to check connectivity and union components.
  • Optimize DSU with path compression and union by rank.

Before this module

M5.10Disjoint Set Union (union-find)M4.2Sorting with keys, and greedy

Lessons

  1. 1Minimum spanning tree and Kruskal with DSU

Practice

Try these on the judges. Each link opens the problem on WMOJ or DMOJ.

  1. 2017 S4
    Minimum Cost Flow (opens on DMOJ in a new tab) DMOJ

    Build a minimum spanning tree while preferring to keep certain edges when costs tie.

    Why DMOJ: An older MST problem, with a DSU-based tie-breaking rule, that still makes good practice for this module.

  2. 2023 S4
    Minimum Cost Roads (opens on WMOJ in a new tab) WMOJ

    A subtask of this problem reduces to a plain minimum spanning tree.