Problem statement

https://binarysearch.com/problems/Flight-Itinerary/

Solution

All we need to do is to find node with indegree 0, this will be start and then traverse all graph.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, flights):
        d1, d2 = {}, {}
        for x, y in flights:
            d1[y] = x
            d2[x] = y

        for x in d2:
            if x not in d1:
                start = x

        path = [start]
        while start in d2:
            start = d2[start]
            path += [start]

        return path