Draw your graph:
function tarjan()
for(v = 0 to
graph.getVertCount())
if(!visited[v])
findSCC(v)
function findSCC(v)
discTime++
disc[v] = discTime
low[v] = discTime
stack.push(v)
for each(neighbour of
v)
if(!visited[neighbour])
findSCC(neighbour)
low[v] =
min(low[v], low[neighbour])
else if(onStack(neighbour))
low[v] =
min(low[v], disc[neighbour])
if(low[v] ==
disc[v])
do
elem =
stack.pop()
addToSCC(elem)
while(elem
!= v)
---------------------
| SHORT EXPLANATION |
---------------------
1. Mark all vertices as unvisited.
2. Run a Depth-first search on every unvisited
vertex.
3. Whenever a DFS begins add the vertex it was run on to
the stack.
4. Maintain two values (disc and low) for each
vertex.
- disc stores the discovery time of the vertex
- low stores the lowest disc reachable from this
vertex
5. Search for vertices with low[v] == disc[v], as these are
the root nodes in the SCC.
6. Pop vertices from the stack until v from step 5 is on
top. The popped vertices are the SCC with root v.
7. Repeat steps 5 and 6 until the stack is empty.