Tarjan's algorithm

PAL Algoritmus input: oriented graph G = (V, E) output: set of strongly connected components

struct Node{
	index
	lowlink   // link to other node in SCC
	pred      // pointer to stack predeccesor
	instack   // true if node is in stack
} 

procedure push( v ) {
	v.pred = S; 
	v.instack = true; 
	S = v;
}

function pop( v ) {
	S = v.pred; 
	v.pred = null; 
	v.instack = false; 
	return v;
}

procedure find_scc( v ) 
	v.index = v.lowlink = ++index; 
	push( v ); 
	
	foreach node w in succ( v ) { 
		if w.index = 0 { // not yet visited 
			find_scc( w ); 
			v.lowlink = min( v.lowlink, w.lowlink ); 
		}
		elsif w.instack {
			v.lowlink = min( v.lowlink, w.index ); 
		}
	} 
	
	if v.lowlink = v.index { // v: head of SCC 
		SCC++ // track how many SCCs found 
		repeat {
			x = pop( S ); 
			add x to current strongly connected component;
		} 
		until x = v; 
		output the current strongly connected component;
	} 
}

index = 0; // unique node number > 0 
S = null; // pointer to node stack 
SCC = 0; // number of SCCs in G 

foreach node v in V {
	if v.index = 0 { // yet unvisited 
		find_scc( v ); 
	}
}