Build original array from the given sub | C # 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
using System ; using System . Collections . Generic ; class GFG { static void addEdge ( List < List < int > > adj , int u , int v ) { adj [ u ] . Add ( v ) ; } static void getindeg ( List < List < int > > adj , int V , List < int > indeg ) { for ( int i = 0 ; i < V ; i ++ ) { foreach ( int x in adj [ i ] ) { indeg [ x ] ++ ; } } } static List < int > topo ( List < List < int > > adj , int V , List < int > indeg ) { Queue < int > q = new Queue < int > ( ) ; for ( int i = 0 ; i < V ; i ++ ) { if ( indeg [ i ] == 0 ) { q . Enqueue ( i ) ; } } List < int > res = new List < int > ( ) ; while ( q . Count > 0 ) { int u = q . Dequeue ( ) ; res . Add ( u ) ; foreach ( int x in adj [ u ] ) { indeg [ x ] -- ; if ( indeg [ x ] == 0 ) { q . Enqueue ( x ) ; } } } return res ; } static List < int > makearray ( List < List < int > > v , int V ) { List < List < int > > adj = new List < List < int > > ( ) ; for ( int i = 0 ; i < V ; i ++ ) { adj . Add ( new List < int > ( ) ) ; } for ( int i = 0 ; i < v . Count ; i ++ ) { for ( int j = 0 ; j < v [ i ] . Count - 1 ; j ++ ) { addEdge ( adj , v [ i ] [ j ] , v [ i ] [ j + 1 ] ) ; } } List < int > indeg = new List < int > ( ) ; for ( int i = 0 ; i < V ; i ++ ) { indeg . Add ( 0 ) ; } getindeg ( adj , V , indeg ) ; List < int > res = topo ( adj , V , indeg ) ; return res ; } static public void Main ( ) { int n = 10 ; List < List < int > > subseqs = new List < List < int > > ( ) ; subseqs . Add ( new List < int > ( ) { 9 , 1 , 2 , 8 , 3 } ) ; subseqs . Add ( new List < int > ( ) { 6 , 1 , 2 } ) ; subseqs . Add ( new List < int > ( ) { 9 , 6 , 3 , 4 } ) ; subseqs . Add ( new List < int > ( ) { 5 , 2 , 7 } ) ; subseqs . Add ( new List < int > ( ) { 0 , 9 , 5 , 4 } ) ; List < int > res = makearray ( subseqs , n ) ; foreach ( int x in res ) { Console . Write ( x + " ▁ " ) ; } } }