I got a weird homework question about graph.
A helicopter is going to land on an island to check the n houses after an earthquake. Some of the two-way roads connecting the houses are destroyed however the helicopter won't know beforehand. Once the the helicopter lands on a house u, they can drive to any neighboring house v if the road (u,v) is not destroyed. The rescue team would only know if a road (u,v) is destroyed or not after they arrive at either u or v. They also don't know the number of safe roads in advance. Design a strategy to minimize the number of helicopter landings, also the plan needs to have less than 2n trips along the safe roads.
My thinking is to do a DFS search on a random unvisted node. After the DFS is done, if there are still unvisited nodes, then do another DFS search from a random unvisited node again. Repeat this until all the nodes are visited. However, I don't know how to prove that this minimize the number of searches. Can anyone help me? Thanks!