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
#include <bits/stdc++.h> NEW_LINE using namespace std ; void addEdge ( vector < int > adj [ ] , int u , int v ) { adj [ u ] . push_back ( v ) ; } void getindeg ( vector < int > adj [ ] , int V , vector < int > & indeg ) { for ( int i = 0 ; i < V ; i ++ ) { for ( auto x : adj [ i ] ) { indeg [ x ] ++ ; } } } vector < int > topo ( vector < int > adj [ ] , int V , vector < int > & indeg ) { queue < int > q ; for ( int i = 0 ; i < V ; i ++ ) { if ( indeg [ i ] == 0 ) q . push ( i ) ; } vector < int > res ; while ( ! q . empty ( ) ) { int u = q . front ( ) ; q . pop ( ) ; res . push_back ( u ) ; for ( auto x : adj [ u ] ) { indeg [ x ] -- ; if ( indeg [ x ] == 0 ) q . push ( x ) ; } } return res ; } vector < int > makearray ( vector < vector < int > > v , int V ) { vector < int > adj [ V ] ; for ( int i = 0 ; i < v . size ( ) ; i ++ ) { for ( int j = 0 ; j < v [ i ] . size ( ) - 1 ; j ++ ) { addEdge ( adj , v [ i ] [ j ] , v [ i ] [ j + 1 ] ) ; } } vector < int > indeg ( V , 0 ) ; getindeg ( adj , V , indeg ) ; vector < int > res = topo ( adj , V , indeg ) ; return res ; } int main ( ) { int n = 10 ; vector < vector < int > > subseqs { { 9 , 1 , 2 , 8 , 3 } , { 6 , 1 , 2 } , { 9 , 6 , 3 , 4 } , { 5 , 2 , 7 } , { 0 , 9 , 5 , 4 } } ; vector < int > res = makearray ( subseqs , n ) ; for ( auto x : res ) { cout << x << " ▁ " ; } return 0 ; }