又是一道拓?fù)渑判虻淖冃晤}, Given org = [1,2,3], seqs = [[1,2],[1,3]]
給一串序列看后面能否組成這個(gè)序列。
思路：拓?fù)渑判虻念}就要記錄鄰接矩陣，然后和每個(gè)點(diǎn)的入度。入度為0放入隊(duì)列，然后取出隊(duì)列里的值，讓它的鄰居入度都減1，如果入度為0的點(diǎn)繼續(xù)放在隊(duì)列里，依次循環(huán)。因?yàn)橥負(fù)渑判蚴侨我廨敵鲆唤M結(jié)果，但這里要求結(jié)果是唯一的。要求不能同時(shí)出現(xiàn)兩個(gè)入度為0的點(diǎn)放入隊(duì)列。所以我們可以設(shè)計(jì)一個(gè)level值來(lái)記錄bfs的層數(shù)。有點(diǎn)像樹(shù)的層級(jí)輸出，并且分層放置。這里面還得加一個(gè)node的set， 來(lái)存放seqs里面的所有node，最后判斷true or false就是判斷是否生成的序列和原序列一致，是否node的個(gè)數(shù)和原序列一致，level長(zhǎng)度和原序列是否一致。
python代碼：

class Solution:
    """
    @param org: a permutation of the integers from 1 to n
    @param seqs: a list of sequences
    @return: true if it can be reconstructed only one or false
    """
    
    def sequenceReconstruction(self, org, seqs):
        # write your code here
        from collections import deque
        neighbor = {}
        indegree = {}
        nodes = set()
        
        for i in org:
            neighbor[i] = []
            indegree[i] = 0
            
        for pair in seqs:
            nodes = nodes | set(pair)
            for i in range(len(pair) - 1):
                if pair[i] not in neighbor or pair[i+1] not in neighbor:
                    return False
                neighbor[pair[i]].append(pair[i+1])
                indegree[pair[i+1]] += 1
        
        queue = deque()
        level = 0
        res = []
        for key in indegree:
            if indegree[key] == 0:
                queue.append(key)
                
        
        
        while queue:
            size = len(queue)
            level += 1
            for _ in range(size):
                node = queue.popleft()
                res.append(node)
                for i in neighbor[node]:
                    indegree[i] -= 1
                    if indegree[i] == 0:
                        queue.append(i)
        
        return res == org and len(nodes) == len(org) and level == len(org)