Algorithm

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.


next up previous
Next: Example Up: STRONGLY CONNECTED COMPONENTS Previous: More Formal Statement