Complete the itinerary

complete_the_itinerary.py

from collections import defaultdict


class Solution(object):

    def solve(self, trips):

        # create a sorted adjacency list from the trips
        graph = defaultdict(list)
        for source, destination in trips:
            graph[source].append(destination)

        for source in graph.keys():
            graph[source] = sorted(graph[source], reverse=True)

        route = []
        stack = ["J"]

        while stack:
            current_city = stack[-1]

            while graph[current_city]:
                current_city = graph[current_city].pop()
                stack.append(current_city)

            route.append(stack.pop())

        route = list(reversed(route))

        return route


if __name__ == "__main__":

    trips = [
        ("J", "A"),
        ("A", "D"),
        ("A", "B"),
        ("B", "C"),
        ("C", "A"),
        ("C", "E"),
        ("E", "C")
    ]

    ans = Solution().solve(trips)
    
    print(ans)