'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List
from collections import deque

class Solution:
    # educative version
    # T: O(V+E) since each number can only be source once and each edge will
    # be accessed and removed once; V for number of distinct numbers
    # E for total number of edges/rules
    # at most, each pair of numbers can give us one rule, we can conclude that 
    # the upper bound for the rules is O(N) where ‘N’ is the count of numbers
    # in all sequences. So, we can say that the time complexity of our algorithm is O(V+N).
    # S: O(V+N), storing all the rules for each number in the graph
    def sequenceReconstruction2(self, org: List[int], seqs: List[List[int]]) -> bool:
        graph = {}
        inDegrees = {}

        for seq in seqs:
            for num in seq:
                graph[num] = []
                inDegrees[num] = 0

        for seq in seqs:
            for i in range(1, len(seq)):
                v1, v2 = seq[i-1], seq[i]
                graph[v1].append(v2)
                inDegrees[v2] += 1

        if len(inDegrees) != len(org):
            return False # dont even have all the numbers in org

        sources = deque()
        for val, ct in inDegrees.items():
            if ct == 0:
                sources.append(val)

        sortedOrder = []
        while sources:
            # for each step, there could be only one source
            # multiple sources mean multiple routes
            if len(sources) > 1:
                return False 
            # the next source(or number) is different from the original sequence
            if org[len(sortedOrder)] != sources[0]:
                return False
            val = sources.popleft()
            sortedOrder.append(val)
            for child in graph[val]:
                inDegrees[child] -= 1
                if inDegrees[child] == 0:
                    sources.append(child)

        if len(sortedOrder) != len(org):
            return False
        return True



    # topology sort
    # https://leetcode.com/problems/sequence-reconstruction/discuss/92580/Java-Solution-using-BFS-Topological-Sort
    def sequenceReconstruction1(self, org: List[int], seqs: List[List[int]]) -> bool:
        values = {x for seq in seqs for x in seq}
        graph = {x: [] for x in values}
        indegrees = {x: 0 for x in values}
        # construct the dependency graph using seqs
        for seq in seqs:
            for i in range(len(seq) - 1):
                s = seq[i]
                t = seq[i+1] # s -> t
                graph[s].append(t)
                indegrees[t] += 1
        
        queue = deque()
        for node, count in indegrees.items():
            if count == 0: # those nodes without any children
                queue.append(node) 
        res = []
        while queue: # check whether there is only one option to select the node
            if len(queue) != 1: # if there is more than one options
                return False
            source = queue.popleft()
            res.append(source)
            for target in graph[source]:
                indegrees[target] -= 1
                if indegrees[target] == 0:
                    queue.append(target)
        # whether its length is the same with number of distinct values and 
        # whether it's the same with org
        return len(res) == len(values) and res == org
        
        
    '''
    two conditions: 1) Every sequence in seqs should be a subsequence in org.
    2) Every 2 consecutive elements in org should be consecutive elements in 
    some sequence from seqs.
    To implement this idea I have idxs hash that maps item to its index in 
    org sequence to check condition 1. And I have pairs set that holds all 
    consequitive element pairs for sequences from seqs to check condition 2 
    (I also consider first elements to be paired with previous undefined 
    elements, it is necessary to check this).
    '''
    def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
        if not seqs: return False
        n = len(org)
        position = [0]*(n+1) # val2index hashing
        for i in range(n):
            # if org[i] <= 0 or org[i] > n: return False # not necessary
            position[org[i]] = i
            
        pairs = [False] * n
        for seq in seqs:
            for i in range(len(seq)):
                if seq[i] <= 0 or seq[i] > n: return False # necessary
                if i == 0 and seq[i] == org[0]:
                    pairs[0] = True
                # the order of consecutive vals in seq is against the order in org
                if i > 0 and position[seq[i-1]] >= position[seq[i]]:
                    return False
                # 2 consecutive vals in org are also consecutive in seg
                if i > 0 and position[seq[i-1]] + 1 == position[seq[i]]:
                    pairs[position[seq[i]]] = True
        
        for i in range(n):
            if not pairs[i]: return False
            
        return True