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.

 

Definition

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

Notes

-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.
 

Constraints

-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.
 

Examples

0)
    
{"1","2","3"}
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).
1)
    
{"1","02","3","4,5"}
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.
2)
    
{"1,2","0,2","1"}
Returns: 6
The only added flight is from 2 to 0.
3)
    
{"1,5,7,8,13,15,16,23,26,35,32,41"
,"0,2,5,6,7,15,18,21,25,31,34,41,49,50"
,"5,10,15,20,25,30,35,40,45,50"}
Returns: 62

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=577

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4373&pm=577

Writer:

chogyonim

Testers:

alexcchan , lbackstrom

Problem categories:

Graph Theory