Disjoint Set Union

Getting Started with Competitive Programming

(an NPTEL course)

Week 4. Disjoint Set Union

In this week, we introduce a popular data structure that's variously known as Union Find, Disjoint Set Union, or simply Disjoint Sets. We implement this data structure with a couple of useful heuristics and encounter a variety of applications.

Class Plan & Materials

A. Prerequisites
1. DSU Foundations
2. Destroying Arrays
3. War
Z. Extras