TopCoder problem "TopPilot" used in TCI '02 Semifinals 4 (Division I Level Two)

Problem Statement


TopPilot airlines is committed to customer service and convenience. Thus, it is not simply enough to have a flight from San Francisco, CA to Hartford, CT. There must be a direct flight.

You will be given a String[] representing one-way flight paths. For each element in the String[], the element index is the departure airport number (0-indexed, so the first element is airport 0) and the element is a comma-delimited list of airport numbers to which there is a direct flight from the departure airport.

Write a method that, given these one-way flight paths, adds direct one-way flights between airports that are currently connected by non-direct one-way flights. For example, if there is a direct flight from SFO to JFK and a direct flight from JFK to LAX, and not a direct flight from SFO to LAX, then add a direct flight from SFO to LAX. Do not, however, add a direct flight from an airport to itself, even if a loop exists. Once this is done, the method should return the total number of flights provided by TopPilot airlines.



Method signature:int addFlights(String[] destinations)
(be sure your method is public)


-If the destination airport does not appear as an element in destinations (which is always the case when it is greater than 19), there are no departing flights from that airport.
-Leading zeroes in the numbers are allowed.


-No airport will have a direct flight to itself.
-destinations will have between 1 and 20 elements, inclusive.
-each element of destinations will contain only the characters '0' through '9', and commas ','.
-each element of destinations will be a comma delimited list of integers, with no numbers repeated, and no leading, trailing, or extra commas.
-each element of destinations will be contain between 1 and 50 characters, inclusive.
-destination airport numbers will be between 0 and 50, inclusive.


Returns: 6
There is a flight from airport 0 to airport 1, from 1 to 2, and from 2 to 3. We add a direct flight from 0 to 2, from 1 to 3, and from 0 to 3 (note that 3 is not an element, so it has no departing flights).
Returns: 14
We add flights from 0 to 2, 3, 4, and 5. We add flights from 1 to 3, 4, and 5. We add flights from 2 to 4 and 5. Together with the 5 flights we already have, there are 14 total.
Returns: 6
The only added flight is from 2 to 0.
Returns: 62

Problem url:

Problem stats url:




alexcchan , lbackstrom

Problem categories:

Graph Theory