Sequence Reconstruction – Python 3 (Week 14 – 10)

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
        graph = self.build_graph(seqs)
        order = self.get_order(graph)
        return order == org
        
        
    def build_graph(self, seqs):
        graph = {}
        #O(m + m) O(n*n)
        for seq in seqs:
            for node in seq:
                if node not in graph:
                    graph[node] = set()
                    
        for seq in seqs:
            for i in range(1, len(seq)):
                graph[seq[i - 1]].add(seq[i])
        return graph
        
        
    def get_order(self, graph):
        # O(n^2)  O(n)
        indegree = self.get_indegree(graph)
        
        queue = []
        #O(n)
        for node in indegree:
            if indegree[node] == 0:
                queue.append(node)
        if len(queue) > 1: #should not use != 1 because case [],[[]]
            return None
            
        order = []
        #O(n*2)
        while queue:
            node = queue.pop()
            order.append(node)
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    queue.append(neighbor)
            if len(queue) > 1:
                return None  
                
        return order if len(order) == len(graph) else None                  
                    
                    
        
    def get_indegree(self, graph):
        indegree = {node: 0 for node in graph}
        
        for node in graph:
            for neighbor in graph[node]:
                indegree[neighbor] += 1
        
        return indegree