Skip to main content

Disjoint Set Union - DSU

Learn Disjoint Set Union - DSU (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Tracking Groups of Connected Elements DSU (also called Union-Find) maintains a collection of disjoint (non-overlapping) sets, supporting two operations: find(x) - which set does x belong to (returns a representative "root"), and union(a, b) - merge a's and b's sets into one. Naive implementation without optimization: each element points to a parent, walking up to the root.

More lessons in Graphs