One-way flight trip implementation in Python I came across the following problem (found on the SO link below):
https://stackoverflow.com/questions/2991950/one-way-flight-trip-problem


  Given a flight trip that includes a number of transfers: we have a
  ticket for each part of the trip; we do not stop twice in the same
  airport; each ticket contains source and destination airport; all the
  tickets we have are randomly sorted, and we forgot the original
  departure airport and the last destination. We want to design an
  algorithm to reconstruct the trip with minimum big-O complexity.


I tried to solve the problem in python in O(n) time complexity. Here is my solution:

L = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'F'), ('F', 'G'), ('G', 'H'), ('H', 'I')]
# Note: the input L should normally be shuffled.

def getDepartureArrival(L):
    sources, destinations = zip(*L)
    sources = set(sources)
    destinations = set(destinations)

    for s in sources:
        if s not in destinations:
            depart = s
            break
    for d in destinations:
        if d not in sources:
            arriv = d
            break
    return depart, arriv
#

def getTrip(H):
    trip = [depart]
    k = depart
    while k != arriv:
        k = H[k]
        trip.append(k)
    return trip
#

depart, arriv = getDepartureArrival(L)
H = {s:d for (s,d) in L}
print getTrip(H)


I would like to know if it is possible to have a clearer and more compact Python code than the one I wrote with more than 4 consecutive loops.
You should not use global variables when not necessary. You can just directly pass depart and arriv to getTrip.

You should strive to have readable variable names. Just use arrival and departure.

Python has an official style-guide, PEP8, which recommends using lower_case_with_underscore for variables and functions.

You can use map to cast both sources and destinations to sets directly. You can also use set subtraction to get the difference value only in one of them.

The dict constructor can directly take an iterable of pairs to build a dictionary.

You can make get_trip a generator, which simplifies the logic slightly.

I would add a if __name__ == "__main__": guard to allow importing stuff from this module without running the whole code. 

import random


def get_departure_arrival(flights):
    """
    Find departure and arrival airport from chain of flights.

    Effectively the opposite of the itertools recipe pairwise:

    &gt;&gt;&gt; get_departure_arrival([(s0, s1), (s1, s2), (s2, s3)])
    (s0, s3)

    Pairs do not have to be in order:

    &gt;&gt;&gt; get_departure_arrival([(s0, s1), (s2, s3), (s1, s2)])
    (s0, s3)
    """
    sources, destinations = map(set, zip(*flights))

    depart = (sources - destinations).pop()
    arriv = (destinations - sources).pop()

    return depart, arriv


def get_trip(flights, depart, arriv):
    """
    Reconstruct a flight trip from pairs of departure and
    arrival airports and the first and last airport of the trip.
    """
    flight_dict = dict(flights)
    while depart != arriv:
        yield depart
        depart = flight_dict[depart]


if __name__ == "__main__":
    flights = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'),
               ('E', 'F'), ('F', 'G'), ('G', 'H'), ('H', 'I')]
    random.shuffle(flights)

    depart, arriv = get_departure_arrival(flights)
    print list(get_trip(flights, depart, arriv))