Sequence Reconstruction

Intuition

Solution

class DiGraph:
    def __init__(self, size):
        self.size = size
        self.adj = [set() for _ in range(size)]

    def add_edge(self, p, q):
        self.adj[p].add(q)


class DFSOrder:
    def __init__(self, digraph):
        self.visited = [False] * digraph.size
        self.postorder = []
        for i in range(digraph.size):
            if not self.visited[i]:
                self.dfs(digraph, i)

    def dfs(self, digraph, vertex):
        self.visited[vertex] = True
        for child in digraph.adj[vertex]:
            if not self.visited[child]:
                self.dfs(digraph, child)
        self.postorder.append(vertex)


class Solution:
    def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
        # convert input to make id in [0, n]
        org = [i - 1 for i in org]
        for s in seqs:
            for i in range(len(s)):
                s[i] -= 1

        # Check if all points are in the subsequences
        inseq = [False] * len(org)
        for s in seqs:
            for v in s:
                if not 0 <= v < len(org):
                    return False
                inseq[v] = True
        if not all(inseq):
            return False

        graph = DiGraph(len(org))
        for s in seqs:
            for i in range(len(s) - 1):
                if s[i + 1] == s[i]:
                    return False
                graph.add_edge(s[i + 1], s[i])

        for i in range(len(org) - 1):
            if org[i] not in graph.adj[org[i + 1]]:
                return False

        order = DFSOrder(graph).postorder
        return org == order