Problem context and objectives
Mission briefing
Expedition navigator · Safe camps and hazards form a connected world map
Find a valid route while marking every place already explored: Island Signals.
Without visited state, the party loops forever or revisits expensive terrain.
How you win
- 1Recognize when Graph traversal matches the clues
- 2Keep this true after every move: every marked node is reachable from the current component start
- 3Reach the result within O(V + E)
Rules and pressure
- Target cost: O(V + E)
- State rule: every marked node is reachable from the current component start
Lesson 1 of 3
Live algorithm trace
Graph traversal
Complete execution1 of 6
0
start
1
2
3
4
Build undirected adjacency lists for five nodes.
1
build adjacency lists2
for each unvisited node3
run DFS or BFS4
components += 1edges = [[0,1], [1,2], [3,4]]seen = {}components = 0
Truth to preserve / Cost target
Truth to preserve
every marked node is reachable from the current component start
Cost target
O(V + E)
A graph traversal marks everything reachable from one starting node. Restarting from each unvisited node counts connected components.
Your call · What should guide every step of this algorithm?