Problem statement

https://binarysearch.com/problems/Recover-Original-List-From-Subsequences/

Solution

Here we need to perform topological sort.

Complexity

It is O(n + E) for time and space.

Code

class Solution:
    def solve(self, seqs):
        pre, suc, verts = defaultdict(int), defaultdict(list), set()
        for seq in seqs:
            for a, b in zip(seq, seq[1:]):
                pre[a] += 1
                suc[b].append(a)
            verts |= set(seq)

        free, out = set(verts) - set(pre), []
        while free:
            a = free.pop()
            out.append(a)
            for b in suc[a]:
                pre[b] -= 1
                if not pre[b]: free.add(b)

        return out[::-1]