Skip to main content
🏗️ Data Structure Builds

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 elements 0..n-1, each in its own set
  • find(x) — return the root (representative) of the set containing x; use path compression (flatten the tree as you traverse)
  • union(x, y) — merge the sets containing x and y; use union by rank (attach the smaller tree under the larger)
  • connected(x, y) — return true if x and y are in the same set
  • componentCount() — return how many disjoint sets currently exist

Stretch goals

  • Return false from union when x and y are 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.