Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Join sets and detect a cycle: The Redundant Road.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Disjoint set union matches the clues
- 2Keep this true after every move: nodes share a root exactly when they are connected
- 3Reach the result within O(E α(V))
Rules and pressure
- Target cost: O(E α(V))
- State rule: nodes share a root exactly when they are connected
Lesson 1 of 3
Live algorithm trace
Disjoint set union
Complete execution1 of 5
0-1
edge
1-2
2-0
Each of the three nodes begins as its own representative.
1
parent = range(n)2
find both roots3
if roots match: cycle4
otherwise union rootsparent = [0, 1, 2]
Truth to preserve / Cost target
Truth to preserve
nodes share a root exactly when they are connected
Cost target
O(E α(V))
Union Find gives every component a representative. If an edge connects two nodes that already share a representative, that edge closes a cycle.
Your call · What should guide every step of this algorithm?