Strongly connected components.

Given below is the strongly connected components algorithm.

Input: Graph G = (V, E)

index = 0                    // DFS node number counter 

S = empty                   // An empty stack of nodes

forall v in V do

  if (v.index is undefined)     // Start a DFS at each node

    tarjan(v)                    // we haven't visited yet

 procedure tarjan(v)

  v.index = index               // Set the depth index for v

  v.lowlink = index

  index = index + 1

  S.push(v)                    // Push v on the stack

  forall (v, v') in E do       // Consider successors of v

    if (v'.index is undefined) // Was successor v' visited?

        tarjan(v')                     // Recurse

        v.lowlink = min(v.lowlink, v'.lowlink)

    else if (v' is in S)       // Was successor v' in stack S? 

        v.lowlink = min(v.lowlink, v'.index )

  if (v.lowlink == v.index)     // Is v the root of an SCC?

    print "SCC:"

    repeat

      v' = S.pop

      print v'

    until (v' == v)

In the above algorithm the graph is traversed using DFS traversal. All the vertices are pushed into the stack as they are visited. Initially v.index and v.lowlink are assigned same values. But v.lowlink is updated for each and every vertex with minimum of the v.lowlink of itself and v.lowlink of the child vertex. If the child vertex can reach the current vertex then the v.lowlink can have least value of v.lowlink. See that as the current vertex is already traversed and therefore present in stack then v.lowlink is updated to its v.index. Hence at the last if the current vertex's index is equal to its lowlink then the current vertex is root of the connected component.