Disjoint Set (Union-Find)
A disjoint set (union-find) is a data structure that keeps track of a set of elements partitioned into disjoint, non-overlapping subsets.
ALL SEPARATE
Four elements, four sets. Every element is its own root, so it points at nothing.
Next
union(0, 1): 1 points at 0. There are now three sets — {0,1}, {2}, {3}.
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. IfFind(x) == Find(y), they are in the same set. - Union(x, y): Merge the set containing
xwith the set containingy. 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".
Applying for software engineering roles? Free, no sign-up: