Union-Find with Path Compression and Union by Rank
Problem statement
Design a Union-Find (disjoint-set) data structure that supports the following operations efficiently:
find(x)-- return the representative (root) of the set containing elementx, using path compression.union(x, y)-- merge the sets containingxandy, using union by rank (or union by size).component_size(x)-- return the number of elements in the set containingx.num_components()-- return the current number of disjoint sets.
All operations should run in near-constant amortized time.
Constraints:
- $1 \leq n \leq 10^6$ (number of elements, labeled $0$ to $n-1$)
- Up to $10^6$ total operations
- Element labels are non-negative integers
Examples:
uf = UnionFind(5) # elements: {0}, {1}, {2}, {3}, {4}
uf.num_components() # => 5
uf.union(0, 1)
uf.union(2, 3)
uf.num_components() # => 3
uf.component_size(0) # => 2
uf.component_size(4) # => 1
uf.union(1, 3)
uf.num_components() # => 2
uf.component_size(0) # => 4
uf.find(3) == uf.find(0) # => True (same component)
Additionally, discuss:
- How integer overflow in the size field can occur with adversarial inputs when using 32-bit integers, and how to guard against it.
- How you would test your implementation with adversarial operation sequences.
Function signature
Implement run_ops(n, ops) where n is the number of elements (labeled 0..n-1) and ops is a list of operations. Each op is a list beginning with its name:
["union", x, y]: merge the sets containingxandy(produces no output)["connected", x, y]: appendTrue/Falsefor whetherxandyare in the same set["component_size", x]: append the size of the set containingx["num_components"]: append the current number of disjoint sets
Return the list of results, one entry per query op (in order); union contributes nothing.
Example
run_ops(3, [["connected", 0, 2], ["union", 0, 1], ["union", 1, 2], ["connected", 0, 2], ["num_components"], ["component_size", 1]]) -> [false, true, 1, 3]
Initially 0 and 2 are separate (false); after unioning 0-1 and 1-2 all three merge, so 0 and 2 are connected (true), there is 1 component, and its size is 3.
Show hint
What single representative could every member of a group agree on, and how would you reach it from any member?
Relevant roles: ML Engineer, AI Engineer, Forward Deployed Engineer and LLM Engineer.