# -*- coding: utf-8 -*-
# Time:  O(n * s), n is the size of org, s is the size of seqs
# Space: O(n)

# Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence
# is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common
# supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of
#  it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.
#
# Example 1:
#
# Input:
# org: [1,2,3], seqs: [[1,2],[1,3]]
#
# Output:
# false
#
# Explanation:
# [1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can
# be reconstructed.
# Example 2:
#
# Input:
# org: [1,2,3], seqs: [[1,2]]
#
# Output:
# false
#
# Explanation:
# The reconstructed sequence can only be [1,2].
# Example 3:
#
# Input:
# org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]
#
# Output:
# true
#
# Explanation:
# The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].
# Example 4:
#
# Input:
# org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]
#
# Output:
# true
# UPDATE (2017/1/8):
# The seqs parameter had been changed to a list of list of strings (instead of a 2d array of strings). Please reload
# the code definition to get the latest changes.
# youtube - https://youtu.be/9iLMxSIShso
import collections


class Solution(object):
    def sequenceReconstruction(self, org, seqs):
        """
        :type org: List[int]
        :type seqs: List[List[int]]
        :rtype: bool
        """
        if len(org) == 0 or len(seqs) == 0:
            return False
        position, visited, count = [0] * (len(org) + 1), [False] * (len(org) + 1), len(org) - 1  # bugfixed

        for i, k in enumerate(org):
            position[k] = i

        existed = False  # bugfixed
        for seq in seqs:
            for i, k in enumerate(seq):
                if not 0 < k <= len(org):
                    return False  # [4,1,5,2,6,3], [1,7] is illegal
                existed = True  # test case [1],[[],[]], you have to enter this loop
                if not i:  # i==0 continue
                    continue
                prev, cur = position[seq[i - 1]], position[k]
                if prev >= cur:
                    return False
                if not visited[cur] and prev + 1 == cur:  # if cur is already arranged, no need to do anything
                    visited[cur], count = True, count - 1

        return count == 0 and existed

    # topoloical sort
    def sequenceReconstruction_topo(self, org, seqs):
        """
        :type org: List[int]
        :type seqs: List[List[int]]
        :rtype: bool
        """
        if len(org) == 0 or len(seqs) == 0:
            return False

        # bugfixed out_nodes = collections.defaultdict(set) => out_nodes = collections.defaultdict(list)
        # org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]], for this test case
        # [5,2] appears 2 times, so the in_degree[2] = 2, so out_nodes[5] should be [2,2], allow duplicates
        out_nodes, in_degree, nodes = collections.defaultdict(list), collections.defaultdict(int), set()
        ord = []

        for seq in seqs:
            # union seq , try to get all node from seq, if org : [1,2,3], seqs :[1,2],[2,3],[3,4],this is wrong
            nodes |= set(seq)
            for i in xrange(len(seq) - 1):
                # out_nodes[seq[i]].add(seq[i+1]) - wrong
                # we should use list here, allow duplicates
                # we record the outcoming nodes and incoming degree
                out_nodes[seq[i]].append(seq[i + 1])
                in_degree[seq[i + 1]] += 1

        que = collections.deque()
        for n in org:
            if in_degree[n] == 0:
                que.append(n)

        # for a correct seq, any time , there will be only on node has 0 incoming degree, otherwise
        # it is wrong
        while len(que) == 1:
            node = que.popleft()
            ord.append(node)

            for n in out_nodes[node]:
                in_degree[n] -= 1
                if in_degree[n] == 0:
                    que.append(n)

        # don't forget to check len(nodes)==len(org), org:[1], seq : [],[], it would return true
        return len(nodes) == len(org) and ord == org

    def sequenceReconstruction2(self, org, seqs):
        """
        :type org: List[int]
        :type seqs: List[List[int]]
        :rtype: bool
        """
        adjacent = collections.defaultdict(list)
        incoming_nodes = collections.defaultdict(int)
        nodes = set()
        for arr in seqs:
            nodes |= set(arr)
            for i in xrange(len(arr)):
                if i == 0:
                    incoming_nodes[arr[i]] += 0
                if i < len(arr) - 1:
                    adjacent[arr[i]].append(arr[i + 1])
                    incoming_nodes[arr[i + 1]] += 1
        cur = [k for k in incoming_nodes if incoming_nodes[k] == 0]
        res = []
        while len(cur) == 1:
            cur_node = cur.pop()
            res.append(cur_node)
            for node in adjacent[cur_node]:
                incoming_nodes[node] -= 1
                if incoming_nodes[node] == 0:
                    cur.append(node)
        if len(cur) > 1:
            return False
        return len(res) == len(nodes) and res == org








if __name__ == '__main__':
    print Solution().sequenceReconstruction([4, 1, 5, 2, 6, 3], [[5, 2, 6, 3], [4, 1, 5, 2]])
    print Solution().sequenceReconstruction([1], [[], []])

    print Solution().sequenceReconstruction_topo([4, 1, 5, 2, 6, 3], [[5, 2, 6, 3], [4, 1, 5, 2]])
    print Solution().sequenceReconstruction_topo([1], [[], []])

    print Solution().sequenceReconstruction2([4, 1, 5, 2, 6, 3], [[5, 2, 6, 3], [4, 1, 5, 2]])
    print Solution().sequenceReconstruction2([1], [[], []])
