Imagine the following problem:

The corporation you work for has just established a number of offices in a foreign land.
But the CEO is worried that corporate strategies and trade secrets will be exposed if
regular telecommunication channels like the internet are used for communication
between these offices. After a long brain–storming session, the Board of Directors came
up with the solution: pigeons.
By nature, pigeons know how to fly to wherever their nest is established. They can also
be trained to fly back to a second location, where their food is regularly delivered. Thus,
messenger pigeons are an effective, hard–to–intercept, point–to–point communication
link. To link two offices, establish a pigeon nest in one office, feed that pigeon in the
other office, and it will learn to fly between the two offices and carry some messages.
The only problem is that pigeons become unreliable over long distances, and the
corporation needs 100% reliability.
You, as the Director of IT, have been charged with verifying if the plan will work. You
consulted biology experts and learned that for distances of up to 200 miles, 100%
reliability can be achieved by well–trained pigeons. Above 200 miles the reliability drops
below 100%, which is not acceptable. Given the geographic locations of the offices, you
calculated direct straight–line distances between all pairs of offices.
Based on all the information you gathered, you need to decide whether any office can
deliver a message to any other office, with 100% reliability, via pigeon post (possibly
using a pigeon relay involving multiple office–to–office hops, with each hop at most 200
miles). You asked your IT team to submit possible options on how to solve the problem,
and you received the following options:

A) Create a graph with one node per office. For each pair of offices, look up the direct
straight–line distance between them, in miles. Add an edge between each pair of
offices, with the distances as edge weights. Run MST on the graph. Inspect the MST,
if all edges in it are below 200 miles, return “yes, pigeon post will work”. If the tree
contains one or more edges with distance above 200 miles, return “no, cannot achieve
100% reliability”.
B) Create a graph with one node per office. For each pair of offices, look up the direct
straight–line distance between them, in miles. If the distance is 200 miles or less, add
an edge between the pair of offices to the graph, if the distance is above 200 miles,
no edge. Run all–pairs shortest path algorithm. If at the end all the vertex–vertex
shortest distances in the graph are finite return “yes, pigeon post will work”. If at least
one pair has “+INF”, return “no, cannot achieve 100% reliability”.
C) Create a graph with one node per office. For each pair of offices, look up the direct
straight–line distance between them, in miles. Add an edge between each pair of
offices, with the distances as edge weights. Run all–pairs shortest path algorithm on
the graph. Inspect the shortest paths between every pair of nodes, if all the edges on all the paths are 200 miles or less, return “yes, pigeon post will work”, if there is one or more edge with weight greater than 200 miles, return “no, cannot achieve100%

reliability”.
D) Create a graph with one node per office. For each pair of offices, look up the direct
straight–line distance between them, in miles. If the distance is 200 miles or less, add
an edge between the pair of offices to the graph, if the distance is above 200 miles,
no edge. Detect if the graph has only one connected component, or more than one:
run depth–first search complexity starting from a random node. If the graph has a
single connected component (all nodes were visited by the DFS without any restarts),
then answer “yes, pigeon post will work”, otherwise answer “no, cannot achieve 100%
reliability”.