vector<int> * StronglyConnectedComponents( Graph G )
{
list<GraphVert*> * L = TopologicalSort( G );
Graph G_t = *(transpose( G ));
for( unsigned int v=0; v < G_t.size(); v++ )
G_t[v]->color = white;
vector<int> * components = new vector<int>( G.size() );
int component = 1;
for( list<GraphVert*>::iterator iter = L->begin();
iter != L->end();
iter++ )
{
list<GraphVert*> * l = new list<GraphVert*>();
int v = (*iter)->num;
if( G_t[v]->color == white )
{
Visit( v, G_t, l );
for( list<GraphVert*>::iterator iter = l->begin();
iter != l->end();
iter++ )
(*components)[ (*iter)->num ] = component;
component++;
}
}
return components;
}
Here, transpose(G) is graph transpose or edge reversal.