Reconstruct Itinerary

Intuition

Solution

class Solution:
    def findItinerary(self, tickets: List[List[str]]) -> List[str]:
        airports = sorted(list(set([t[0] for t in tickets] + [t[1] for t in tickets])))
        tickets.sort()
        size = len(airports)

        indexes = {}
        for i, name in enumerate(airports):
            indexes[name] = i

        graph = DiGraph(size)
        for p, q in tickets:
            graph.add_edge(indexes[p], indexes[q])

        self.postorder = []
        self.dfs(graph, indexes['JFK'])
        return [airports[i] for i in self.postorder[::-1]]

    def dfs(self, graph, vertex):
        for i, child in enumerate(graph.adj[vertex]):
            if not graph.used[vertex][i]:
                graph.used[vertex][i] = True
                self.dfs(graph, child)
        self.postorder.append(vertex)