Skip to content
CCC Python Course

Disjoint Set Union (union-find)

Stage
5
Module
M5.10
Lessons
1

In this module

  • Implement find with path halving to track connectivity across components.
  • Apply union by size to keep the tree shallow and fast.
  • Use the "next free slot" DSU trick to solve resource allocation problems.
  • Recognize when DSU contracts components for efficient solutions.

Before this module

M1.8Lists (1D and 2D)M1.10Functions and scope

Lessons

  1. 1Disjoint Set Union (union-find)

Practice

Try these on the judge. Each link opens the problem on DMOJ.

  1. 2015 S3
    Gates (opens on DMOJ in a new tab) DMOJ

    Find the next available gate on a linear arrangement using DSU next-free optimization.

    Why DMOJ: A direct application of the next-free-slot trick from this module.

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

    Merge components with DSU while breaking ties between equally cheap connections.

    Why DMOJ: The full problem builds a minimum spanning tree, a later module's topic, but its DSU merging step is good practice here.