Disjoint Set (Union-Find)
A data structure that keeps track of a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
Initially, every element is its own set (its own parent).
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Imagine a group of people. Initially, everyone is a stranger (their own set). If A becomes friends with B, their entire groups merge.
We need a way to quickly answer: "Are X and Y connected?" and "Merge the group of X with the group of Y". The Union-Find data structure does this extremely fast, almost in constant time!
Concept
Core Operations:
- Find(x): Identify the "representative" (leader) of the set containing `x`. If `Find(x) == Find(y)`, they are in the same set.
- Union(x, y): Merge the set containing `x` with the set containing `y`. This usually involves setting the parent of one leader to the other.
How it Works
The structure is a forest of trees. Each node points to its parent. The root points to itself.
- Initialization: `parent[i] = i`. Everyone is their own leader.
- Union(1, 2): `parent[2] = 1`. 1 is now the leader of {1, 2}.
- Find(2): Follow pointers up: `2 -> 1 -> 1`. Leader is 1.
Step-by-Step Breakdown
1. Initialize `parent` array.
2. To Find `x`: Walk up until `parent[node] == node`.
3. To Union `x, y`: Find leaders `rootX = Find(x)`, `rootY = Find(y)`. If different, set `parent[rootY] = rootX`.
When to Use
- Connected Components in a graph.
- Kruskal's Algorithm for MST.
- Cycle detection in undirected graphs.
- Image processing (labeling regions).
When NOT to Use
- When you need to un-merge (Union-Find usually doesn't support splitting).
- Directed graphs (usually need DFS/BFS for reachability).
How to Identify
"Groups of connected items", "Merge communities", "Check connectivity dynamically".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.