// a node in Tarjan's notation has associated array structures, indexed

// by node ID; these arrays are lowlink() and number(). Also, there

// is a stack of nodes. The stack, the arrays, and an integer counter

// scc_number are globally visible

int scc_number;

procedure scc( v )

{ // scc

lowlink(v) := number(v) := ++scc_number

push( v )

for all successors w of v do

if w is not visited then -- v->w is a tree arc

scc( w )

lowlink(v) := min( lowlink(v), lowlink(w) )

elsif number(w) < number(v) then -- v->w is cross link

if in_stack(w) then

lowlink(v) := min( lowlink(v), number(w) )

end if

end if

end for

if lowlink(v) = number(v) then -- next scc found

while w := top_of_stack_node; number(w) >= number(v) do

pop(w)

end while

end if

} // end scc

procedure main()

{ // main

scc_number := 0

empty the stack

mark all nodes in G as 'not visited'

for each node in G that is not visited, do

scc( w )

end for

} // end main
