Advanced · Module 18 · Lesson 1 of 4
Disjoint sets
Union-find keeps elements in groups that only ever merge. Each group is a tree of parent pointers, its root names the group, and two questions, which group is x in and merge these two groups, cover a surprising range of problems.
By the end you can
- Represent groups as a forest of parent pointers, with the root as each group's name
- Implement find and union, and use them to answer connectivity queries as edges arrive
- Count components and detect the edge that closes a cycle
Builds on Cycles and connected components.
01 · A question first
A social network adds a million friendships a minute and must answer "are these two people connected through friends?" after each one. Re-running a graph search for every question is far too slow. An array of parent pointers answers in nearly constant time. How can a structure that only ever merges groups do that?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Groups that only merge
- A forest of parent pointers
- What it is good for
- Worked example: the redundant edge
- Union-find or a graph search?
- The weakness
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Something wrong with this lesson? Report a problem