# Computing the strongly connected components using Tarjan's algorithm
private class TarjanAlgorithm[V: Object]
	# The graph whose strongly connected components will be computed
	var graph: Digraph[V]
	# The strongly connected components computed in Tarjan's algorithm
	var sccs = new DisjointSet[V]
	# An index used for Tarjan's algorithm
	var index = 0
	# A stack used for Tarjan's algorithm
	var stack: Queue[V] = (new Array[V]).as_lifo
	# A map associating with each vertex its index
	var vertex_to_index = new HashMap[V, Int]
	# A map associating with each vertex its ancestor in Tarjan's algorithm
	var ancestor = new HashMap[V, Int]
	# True if and only if the vertex is in the stack
	var in_stack = new HashSet[V]

	# Returns the strongly connected components of a graph
	fun strongly_connected_components: DisjointSet[V]
	do
		for u in graph.vertices_iterator do sccs.add(u)
		for v in graph.vertices_iterator do
			visit(v)
		end
		return sccs
	end

	# The recursive part of Tarjan's algorithm
	fun visit(u: V)
	do
		vertex_to_index[u] = index
		ancestor[u] = index
		index += 1
		stack.add(u)
		in_stack.add(u)
		for v in graph.successors(u) do
			if not vertex_to_index.keys.has(v) then
				visit(v)
				ancestor[u] = ancestor[u].min(ancestor[v])
			else if in_stack.has(v) then
				ancestor[u] = ancestor[u].min(vertex_to_index[v])
			end
		end
		if vertex_to_index[u] == ancestor[u] then
			var v
			loop
				v = stack.take
				in_stack.remove(v)
				sccs.union(u, v)
				if u == v then break
			end
		end
	end
end