Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Merge direct roads into connected regions: The Province Roots.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Union Find component counting matches the clues
- 2Keep this true after every move: two cities share a root exactly when processed roads connect them
- 3Reach the result within O(n squared alpha(n))
Rules and pressure
- Target cost: O(n squared alpha(n))
- State rule: two cities share a root exactly when processed roads connect them
Lesson 1 of 3
Live algorithm trace
Union Find component counting
Complete execution1 of 6
0
city
1
2
Initialize three singleton city sets.
1
parent = range(n); count = n2
scan the upper matrix triangle3
find both city roots4
if roots differ: union them5
count -= 1 after a merge6
return countparent = [0,1,2]count = 3
Truth to preserve / Cost target
Truth to preserve
two cities share a root exactly when processed roads connect them
Cost target
O(n squared alpha(n))
Begin with one set per city. Every direct road unions two roots; only a successful merge reduces the component count, leaving exactly one representative per province.
Your call · What should guide every step of this algorithm?