Build original array from the given sub | Java 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 ; Driver code ; Size of the required array ; Given sub - sequences of the array ; Get the resultant array as vector ; Printing the array
import java . io . * ; import java . util . * ; class GFG { static void addEdge ( ArrayList < ArrayList < Integer > > adj , int u , int v ) { adj . get ( u ) . add ( v ) ; } static void getindeg ( ArrayList < ArrayList < Integer > > adj , int V , ArrayList < Integer > indeg ) { for ( int i = 0 ; i < V ; i ++ ) { for ( int x : adj . get ( i ) ) { indeg . set ( x , indeg . get ( x ) + 1 ) ; } } } static ArrayList < Integer > topo ( ArrayList < ArrayList < Integer > > adj , int V , ArrayList < Integer > indeg ) { Queue < Integer > q = new LinkedList < > ( ) ; for ( int i = 0 ; i < V ; i ++ ) { if ( indeg . get ( i ) == 0 ) { q . add ( i ) ; } } ArrayList < Integer > res = new ArrayList < Integer > ( ) ; while ( q . size ( ) > 0 ) { int u = q . poll ( ) ; res . add ( u ) ; for ( int x : adj . get ( u ) ) { indeg . set ( x , indeg . get ( x ) - 1 ) ; if ( indeg . get ( x ) == 0 ) { q . add ( x ) ; } } } return res ; } static ArrayList < Integer > makearray ( ArrayList < ArrayList < Integer > > v , int V ) { ArrayList < ArrayList < Integer > > adj = new ArrayList < ArrayList < Integer > > ( ) ; for ( int i = 0 ; i < V ; i ++ ) { adj . add ( new ArrayList < Integer > ( ) ) ; } for ( int i = 0 ; i < v . size ( ) ; i ++ ) { for ( int j = 0 ; j < v . get ( i ) . size ( ) - 1 ; j ++ ) { addEdge ( adj , v . get ( i ) . get ( j ) , v . get ( i ) . get ( j + 1 ) ) ; } } ArrayList < Integer > indeg = new ArrayList < Integer > ( ) ; for ( int i = 0 ; i < V ; i ++ ) { indeg . add ( 0 ) ; } getindeg ( adj , V , indeg ) ; ArrayList < Integer > res = topo ( adj , V , indeg ) ; return res ; } public static void main ( String [ ] args ) { int n = 10 ; ArrayList < ArrayList < Integer > > subseqs = new ArrayList < ArrayList < Integer > > ( ) ; subseqs . add ( new ArrayList < Integer > ( Arrays . asList ( 9 , 1 , 2 , 8 , 3 ) ) ) ; subseqs . add ( new ArrayList < Integer > ( Arrays . asList ( 6 , 1 , 2 ) ) ) ; subseqs . add ( new ArrayList < Integer > ( Arrays . asList ( 9 , 6 , 3 , 4 ) ) ) ; subseqs . add ( new ArrayList < Integer > ( Arrays . asList ( 5 , 2 , 7 ) ) ) ; subseqs . add ( new ArrayList < Integer > ( Arrays . asList ( 0 , 9 , 5 , 4 ) ) ) ; ArrayList < Integer > res = makearray ( subseqs , n ) ; for ( int x : res ) { System . out . print ( x + " ▁ " ) ; } } }