Build original array from the given sub | Python3 implementation of the approach ; Function to add edge to graph ; Function to calculate indegrees of all the vertices ; If there is an edge from i to x then increment indegree of x ; Function to perform topological sort ; Push every node to the queue which has no incoming edge ; Since edge u is removed , update the indegrees of all the nodes which had an incoming edge from u ; Function to generate the array from the given sub - sequences ; Create the graph from the input sub - sequences ; Add edge between every two consecutive elements of the given sub - sequences ; Get the indegrees for all the vertices ; Get the topological order of the created graph ; Size of the required array ; Given sub - sequences of the array ; Get the resultant array as vector ; Printing the array
from collections import deque NEW_LINE adj = [ [ ] for i in range ( 100 ) ] NEW_LINE def addEdge ( u , v ) : NEW_LINE INDENT adj [ u ] . append ( v ) NEW_LINE DEDENT def getindeg ( V , indeg ) : NEW_LINE INDENT for i in range ( V ) : NEW_LINE INDENT for x in adj [ i ] : NEW_LINE INDENT indeg [ x ] += 1 NEW_LINE DEDENT DEDENT DEDENT def topo ( V , indeg ) : NEW_LINE INDENT q = deque ( ) NEW_LINE for i in range ( V ) : NEW_LINE INDENT if ( indeg [ i ] == 0 ) : NEW_LINE INDENT q . appendleft ( i ) NEW_LINE DEDENT DEDENT res = [ ] NEW_LINE while ( len ( q ) > 0 ) : NEW_LINE INDENT u = q . popleft ( ) NEW_LINE res . append ( u ) NEW_LINE for x in adj [ u ] : NEW_LINE INDENT indeg [ x ] -= 1 NEW_LINE if ( indeg [ x ] == 0 ) : NEW_LINE INDENT q . appendleft ( x ) NEW_LINE DEDENT DEDENT DEDENT return res NEW_LINE DEDENT def makearray ( v , V ) : NEW_LINE INDENT for i in range ( len ( v ) ) : NEW_LINE INDENT for j in range ( len ( v [ i ] ) - 1 ) : NEW_LINE INDENT addEdge ( v [ i ] [ j ] , v [ i ] [ j + 1 ] ) NEW_LINE DEDENT DEDENT indeg = [ 0 for i in range ( V ) ] NEW_LINE getindeg ( V , indeg ) NEW_LINE res = topo ( V , indeg ) NEW_LINE return res NEW_LINE DEDENT n = 10 NEW_LINE subseqs = [ [ 9 , 1 , 2 , 8 , 3 ] , [ 6 , 1 , 2 ] , [ 9 , 6 , 3 , 4 ] , [ 5 , 2 , 7 ] , [ 0 , 9 , 5 , 4 ] ] NEW_LINE res = makearray ( subseqs , n ) NEW_LINE for x in res : NEW_LINE INDENT print ( x , end = " ▁ " ) NEW_LINE DEDENT