#include<bits/stdc++.h>
using namespace std;
map< int , string> mp;
class Graph
{
int V; list< int > * adj;
public :
Graph( int ) ;
void addEdge( int , int ) ;
void DFS( int , vector< bool > & , vector< int > & , int & ) ;
void topologicalSort( ) ;
} ;
Graph:: Graph ( int V)
{
this- > V = V;
adj = new list< int > [ V] ;
}
void Graph:: addEdge ( int v, int w)
{
adj[ v] .push_back ( w) ;
}
void Graph:: DFS ( int v, vector< bool > & explored, vector< int > & finish, int & time )
{
explored[ v] = true ;
for ( int i : adj[ v] )
if ( ! explored[ i] )
DFS( i, explored, finish, time ) ;
finish[ ++ time ] = v;
}
void Graph:: topologicalSort ( )
{
vector< int > finish( V, - 1 ) ;
vector< bool > explored( V, false ) ;
int time = - 1 ;
for ( int i = 0 ; i < V; i++ )
if ( ! explored[ i] )
DFS( i, explored, finish, time ) ;
for ( int i = V - 1 ; i >= 0 ; i-- )
cout << mp[ finish[ i] ] << "\n " ;
}
int main( )
{
mp.insert ( { 0 , "Review Board" } ) ;
mp.insert ( { 1 , "Hospitality" } ) ;
mp.insert ( { 2 , "Registration" } ) ;
mp.insert ( { 3 , "Finance" } ) ;
mp.insert ( { 4 , "Session" } ) ;
mp.insert ( { 5 , "Approval from TEQIP coordinatopr" } ) ;
mp.insert ( { 6 , "Food" } ) ;
mp.insert ( { 7 , "Paper" } ) ;
mp.insert ( { 8 , "Poster" } ) ;
mp.insert ( { 9 , "Approval from Director" } ) ;
Graph g( 10 ) ;
g.addEdge ( 2 , 0 ) ;
g.addEdge ( 7 , 0 ) ;
g.addEdge ( 8 , 0 ) ;
g.addEdge ( 3 , 1 ) ;
g.addEdge ( 6 , 1 ) ;
g.addEdge ( 3 , 2 ) ;
g.addEdge ( 5 , 3 ) ;
g.addEdge ( 0 , 4 ) ;
g.addEdge ( 9 , 5 ) ;
g.addEdge ( 3 , 6 ) ;
cout << "Topological Sort of the given graph is \n " ;
g.topologicalSort ( ) ;
return 0 ;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4gCnVzaW5nIG5hbWVzcGFjZSBzdGQ7IAoKbWFwPGludCwgc3RyaW5nPiBtcDsKY2xhc3MgR3JhcGggCnsgCglpbnQgVjsgCWxpc3Q8aW50PiogYWRqOyAKCXB1YmxpYzogCgkJR3JhcGgoaW50KTsKCQoJCXZvaWQgYWRkRWRnZShpbnQsIGludCk7IAoJCgkJdm9pZCBERlMoaW50LCB2ZWN0b3I8Ym9vbD4gJiwgdmVjdG9yPGludD4gJiwgaW50ICYpOyAKCQl2b2lkIHRvcG9sb2dpY2FsU29ydCgpOyAKfTsgCgpHcmFwaDo6R3JhcGgoaW50IFYpIAp7IAoJdGhpcy0+ViA9IFY7IAoJYWRqID0gbmV3IGxpc3Q8aW50PltWXTsgCn0gCgoKdm9pZCBHcmFwaDo6YWRkRWRnZShpbnQgdiwgaW50IHcpIAp7IAoJYWRqW3ZdLnB1c2hfYmFjayh3KTsgCn0gCgoKdm9pZCBHcmFwaDo6REZTKGludCB2LCB2ZWN0b3I8Ym9vbD4gJmV4cGxvcmVkLCB2ZWN0b3I8aW50PiAmZmluaXNoLCBpbnQgJnRpbWUpIAp7IAoJZXhwbG9yZWRbdl0gPSB0cnVlOyAKCQlmb3IoaW50IGkgOiBhZGpbdl0pIAoJCWlmKCFleHBsb3JlZFtpXSkgCgkJCURGUyhpLCBleHBsb3JlZCwgZmluaXNoLCB0aW1lKTsgCgoJZmluaXNoWysrdGltZV0gPSB2OyAKfSAKCnZvaWQgR3JhcGg6OnRvcG9sb2dpY2FsU29ydCgpIAp7IAoJdmVjdG9yPGludD4gZmluaXNoKFYsIC0xKTsgCgoJdmVjdG9yPGJvb2w+IGV4cGxvcmVkKFYsIGZhbHNlKTsgCglpbnQgdGltZSA9IC0xOyAKCglmb3IoaW50IGkgPSAwOyBpIDwgVjsgaSsrKSAKCQlpZighZXhwbG9yZWRbaV0pIAoJCQlERlMoaSwgZXhwbG9yZWQsIGZpbmlzaCwgdGltZSk7IAoJCglmb3IoaW50IGkgPSBWIC0gMTsgaSA+PSAwOyBpLS0pIAoJCWNvdXQgPDwgbXBbZmluaXNoW2ldXSA8PCAiXG4gIjsgCn0gCgoKaW50IG1haW4oKSAKeyAKCQoJbXAuaW5zZXJ0KHsgMCwgIlJldmlldyBCb2FyZCIgfSk7IAoJbXAuaW5zZXJ0KHsgMSwgIkhvc3BpdGFsaXR5IiB9KTsgCgltcC5pbnNlcnQoeyAyLCAiUmVnaXN0cmF0aW9uIiB9KTsgCgltcC5pbnNlcnQoeyAzLCAiRmluYW5jZSIgfSk7IAoJbXAuaW5zZXJ0KHsgNCwgIlNlc3Npb24iIH0pOyAKCW1wLmluc2VydCh7IDUsICJBcHByb3ZhbCBmcm9tIFRFUUlQIGNvb3JkaW5hdG9wciIgfSk7IAoJbXAuaW5zZXJ0KHsgNiwgIkZvb2QiIH0pOyAKCW1wLmluc2VydCh7IDcsICJQYXBlciIgfSk7IAoJbXAuaW5zZXJ0KHsgOCwgIlBvc3RlciIgfSk7IAoJbXAuaW5zZXJ0KHsgOSwgIkFwcHJvdmFsIGZyb20gRGlyZWN0b3IiIH0pOyAKCglHcmFwaCBnKDEwKTsgCglnLmFkZEVkZ2UoMiwgMCk7IAoJZy5hZGRFZGdlKDcsIDApOyAKCWcuYWRkRWRnZSg4LCAwKTsgCglnLmFkZEVkZ2UoMywgMSk7IAoJZy5hZGRFZGdlKDYsIDEpOyAKCWcuYWRkRWRnZSgzLCAyKTsgCglnLmFkZEVkZ2UoNSwgMyk7CglnLmFkZEVkZ2UoMCwgNCk7CglnLmFkZEVkZ2UoOSwgNSk7CglnLmFkZEVkZ2UoMywgNik7CgoJY291dCA8PCAiVG9wb2xvZ2ljYWwgU29ydCBvZiB0aGUgZ2l2ZW4gZ3JhcGggaXMgXG4iOyAKCWcudG9wb2xvZ2ljYWxTb3J0KCk7IAoKCXJldHVybiAwOyAKfSAK