I have a strange question about the task.
A helicopter will land on an island to check the houses after an earthquake. Some of the two-lane roads that connect the houses are destroyed, however, the helicopter will not know beforehand. Once the helicopter lands in a house u, they can drive to any neighboring house and if the road (u, v) is not destroyed. The rescue team would only know if a road (u, v) is destroyed or not after landing in u or v. They also do not know the amount of safe roads in advance. Design a strategy to minimize the number of helicopter landings, in addition, the plan must have fewer than 2 trips on safe roads.
My thought is to do a DFS search on a random unassisted node. Once the DFS is done, if there are still unvisited nodes, perform another DFS search from an unvisited random node. Repeat this until all the nodes are visited. However, I do not know how to show that this minimizes the number of searches. Can anybody help me? Thank you!