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.