Problem context and objectives
Mission briefing
Realm network architect · Routes have costs, dependencies, and unreliable bridges
Choose the next frontier that preserves the route guarantee: The Kruskal Grid.
One locally tempting edge can invalidate the whole journey.
How you win
- 1Recognize when Kruskal with Union Find matches the clues
- 2Keep this true after every move: accepted edges form an acyclic forest contained in some minimum spanning tree
- 3Reach the result within O(E log E)
Rules and pressure
- Target cost: O(E log E)
- State rule: accepted edges form an acyclic forest contained in some minimum spanning tree
Lesson 1 of 3
Live algorithm trace
Kruskal with Union Find
Complete execution1 of 6
0-1:1
edge
1-2:2
0-2:3
2-3:4
Sort edges ascending and initialize four singleton components.
1
sort edges by weight2
make one set per node3
for each edge4
if roots differ: accept edge5
union roots and add weight6
stop after n - 1 edges7
return cost or -1components = 4total = 0
Truth to preserve / Cost target
Truth to preserve
accepted edges form an acyclic forest contained in some minimum spanning tree
Cost target
O(E log E)
Sort edges by weight. An edge between different components is the cheapest available bridge across that cut; accept it and union the roots, while rejecting cycle-forming edges.
Your call · What should guide every step of this algorithm?