What you're building
A Union-Find (Disjoint Set Union) data structure that tracks which elements belong to the same connected group. Real uses:
- "Are Alice and Bob connected on LinkedIn?" (social graph reachability)
- Kruskal's minimum spanning tree algorithm
- Detecting cycles in a graph
- Pixel flood-fill / image segmentation
- Network cluster detection
Requirements
new UnionFind(n)— create a structure for elements0..n-1, each in its own setfind(x)— return the root (representative) of the set containingx; use path compression (flatten the tree as you traverse)union(x, y)— merge the sets containingxandy; use union by rank (attach the smaller tree under the larger)connected(x, y)— returntrueifxandyare in the same setcomponentCount()— return how many disjoint sets currently exist
Stretch goals
- Return
falsefromunionwhenxandyare already in the same set (useful for cycle detection) - Add a
getComponents()method returning an array of arrays, each being the members of one set
What this proves
You can implement a near-O(1) amortized structure with two classic optimizations (path compression + union by rank), and you understand how graph connectivity is tracked efficiently at scale.
⚡ 60 XP
solution.jsRuns in your browser
Loading editor…
Tests4 to pass
all elements start disconnected
union merges components
connected returns false for separate sets
full merge reaches one component
Run your code to check these.