So I learned about Tarjan's algorithm the other day and I'm not quite sure if I understand it 100% correctly. I read a lot about the statement that Tarjan's algorithm is able to decompose a directed graph (digraph) into its strongly connected components (SCCs). An SCC being defined as a partition of the digraph with the condition that all of the component's nodes can be reached from every other node in that component.
Suppose I have the following digraph:
To my understanding, the graph has two SCCs: one formed by the three nodes to the left, the second by the three nodes to the right. If I understand Tarjan's algorithm correctly however, it will only detect the "left" SCC, because the "right" one does not contain a cycle, is that correct? In this case, the statement that Tarjan's algorithm finds SCCs is not entirely correct?
Best Answer
I did a quick and dirty python implementation of the algorithm as described in the Wikipedia article, and tested it on your digraph.
This outputs
so the algorithm does indeed work in this case. The algorithm is very well known, and the chance that it is incorrect is negligible.