Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Attach the smaller tree beneath the larger: The Weighted Clusters.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Union by size matches the clues
- 2Keep this true after every move: size[root] equals the number of nodes in that root's component
- 3Reach the result within O((n + e) alpha(n))
Rules and pressure
- Target cost: O((n + e) alpha(n))
- State rule: size[root] equals the number of nodes in that root's component
Lesson 1 of 3
Live algorithm trace
Union by size
Complete execution1 of 6
0-1
root
2-3
1-2
4-5
Initialize six singleton weighted components.
1
parent = range(n); size = ones2
find both roots3
swap so rootA is larger4
parent[rootB] = rootA5
size[rootA] += size[rootB]6
collect sizes at roots7
sort descendingparent = [0,1,2,3,4,5]sizes = all 1
Truth to preserve / Cost target
Truth to preserve
size[root] equals the number of nodes in that root's component
Cost target
O((n + e) alpha(n))
Track each root's component size. When two roots differ, attach the smaller component beneath the larger root, update only the surviving root's size, and keep trees shallow.
Your call · What should guide every step of this algorithm?