Strong connectivity algorithm Define the DFS numbering dfsnum(v) to be the number of vertices visited before v in the DFS. Then if there is a back or cross edge out of the subtree of v, it's to something visited before v and therefore with a smaller dfsnum. We use this by defining the low value low(v) to be the smallest dfsnum of a vertex reachable by a back or cross edge from the subtree of v. If there is no such edge, low(v)=dfsnum(v). Then rephrasing what we've seen so far, v is a head of a component exactly when low(v)=dfsnum(v). The advantage of using these definitions is that dfsnum(v) is trivial to calculate as we perform the DFS, and low(v) is easily computed by combining the low values from the children of v with the values coming from back or cross edges out of v itself.

We use one more simple data structure, a stack L (represented as a list) which we use to identify the subtree rooted at a vertex. We simply push each new vertex onto L as we visit it; then when we have finished visiting a vertex, its subtree will be everything pushed after it onto L. If v is a head, and we've already deleted the other heads in that subtree, the remaining vertices left on L will be exactly the component [v].

We are now ready to describe the actual algorithm. It simply performs a DFS, keeping track of the low and dfsnum values defined above, using them to identify heads of components, and when finding a head deleting the whole component from the graph, using L to find the vertices of the component.

    DFS(G)
   {
   make a new vertex x with edges x->v for all v
   initialize a counter N to zero
   initialize list L to empty
   build directed tree T, initially a single vertex {x}
   visit(x)
   }

   visit(p)
   {
   add p to L
   dfsnum(p) = N
   increment N
   low(p) = dfsnum(p)
   for each edge p->q
       if q is not already in T
       {
       add p->q to T
       visit(q)
       low(p) = min(low(p), low(q))
       } else low(p) = min(low(p), dfsnum(q))

   if low(p)=dfsnum(p)
   {
       output "component:"
       repeat
       remove last element v from L
       output v
       remove v from G
       until v=p
   }
   }

  ¶ 12:33 PM