CMI2014-B-03

Question

$\text{Air CMI }$operates direct flights between different cities. For any pair of cities $A$ and $B$, there is at most one flight in a day from $A$ to $B$. The online site $FakeTrip$ is tryingto compile a list of all routes available through $\text{Air CMI}$.

1. $FakeTrip$ has a table of all direct flights operated by $\text{Air CMI}$. From this, it wants to prepare a list of all pairs of cities connected by a sequence of flights. Describe an algorithm for this and analyze the complexity of your algorithm.
2. $CheapTricks$ is trying to enter the market by improving on $FakeTrip$. $CheapTricks$ has realized that not all connections listed by $FakeTrip$ are feasible because of arrival and departure constraints. $A$ connection from $A$ to $B$ to $C$ is possible if the scheduled arrival of the flight from $A$ to $B$ is at least one hour before the scheduled departure of the flight from $B$ to $C$.

Given a table of direct flights with scheduled arrival and departure times, describe an algorithm for $CheapTricks$ to list all pairs of cities connected by a route on which all connections are feasible within the same day. Analyze the complexity of your algorithm.

Answer 1