DSA TrainerFoundations · Unit 12
Union-Find
Imagine a social network where friendships keep getting added, and at any moment you might be asked: are these two people in the same connected circle? You could run a fresh BFS or DFS for every question, but if the connections keep changing and the questions keep coming, that is a lot of repeated work.
Union-Find, also called Disjoint Set Union, is built exactly for this. It keeps a collection of groups and supports two operations blisteringly fast: union, which merges two groups, and find, which tells you which group something belongs to. Ask "are X and Y connected?" and it answers by checking whether they share a group, in nearly constant time.
The structure is a forest: each group is a little tree, and every element points toward a representative root. This unit builds it up, find, union, and the two optimizations that make it near-instant, and then draws the line between when union-find is the right tool and when a plain BFS or DFS is.
You’re not signed in. Your progress here won’t be saved.
The problem: are these two connected?
You are given a network where connections are added over time, and a stream of questions like "are node 3 and node 8 in the same group?" or "merge the groups of 3 and 8." This is dynamic connectivity.
Running a BFS or DFS from scratch for each connectivity question works, but each one is O(nodes + edges), and with many questions that piles up fast. Union-Find answers each query in nearly constant time after cheap setup, which is the whole reason it exists.
Union-Find is designed for which situation?
The drills and graded test are premium
The lessons above are free. The interactive practice that turns recognizing the pattern into recalling it on a blank page unlocks with premium:
- ✓3 applied drills: train spotting when the concept applies
- ✓A 5-question graded test to clear the unit
- ✓The full guided problem ladder with faded hints, plus the cold-read capstone
From $6/month. Cancel anytime.