1. DSU Foundations

Competitive ProgrammingWeek 04

This is a module in three parts.

DSU — Definition and Motivation

In this lecture, we introduce the Disjoint Set Union data structure and motivate it by showing how it can be used to track the connected components of a graph as edges get added to an empty set of vertices over time.

You can find out more about the DSU data structure in this book chapter by Jeff Erickson or these notes here.

DSU via Union by Rank and Path Compression

In this lecture, we discuss some approaches to implementing Disjoint Sets Union. After ruling out a couple of naive approaches, we describe the heuristics of:

  1. Union by depth, and
  2. Path compression + union by rank

We do not prove the theoretical guarantees promised by these approaches. If you are interested in the proofs, please refer to this book chapter by Jeff Erickson.

DSU - Implementation

In this video we implement the path compression and union by rank heuristics described in the previous video. You can try these problems out yourself by going to the Codeforces website, and clicking on the EDU tab, and enrolling in the “ITMO Academy: pilot course”. The following links will only work if you are already logged in and enrolled in this course. The course is free to enroll in.