[Java] Path based algorithm for finding strongly connected components in a graph

We've already seen both Tarjan's and Kosaraju's algorithms for finding the strongly connected components in a graph. We now take a look at another easy implementation, the path-based algorithm. 

Supposedly, Dijkstra was the first one to propose a O(V + E) time solution to the problem. I could find a reference to his idea in the book "A discipline of programming" chapter 25 page 192.

The idea behind this algorithm is similar to what we saw in Tarjan's solution however there are small differences:

• we still have a global counter which is used to track the preorder number of each node we visit
• we now use two stacks to track all nodes visited in the order they have been visited (S) and all nodes not yet added to a SCC (P)
  
• in Tarjan's approach we determine whether we're following a back link or cross link by looking at the content of the stack (we used a Set for this to improve performance) while in the path-based approach we look at the discovered SCCs. Again to improve performance, I used a marker value for preorder number of a node to flag whether it was added to a SCC or not. Therefore in both cases this check is O(1) at the cost of O(V) space.
  
• in Tarjan's approach, after visiting a subgraph from a node, we would update its lowest discovery time using the new information calculated during the visit. With the path-based approach instead we remove nodes from the P stack until we leave the potential head of an SCC on its top
• in both approaches, before backtracking we verify if the current node is the head of a SCC. In Tarjan's case, we compare the discovery time and lowest discovery time of the node, while in the path-based approach we compare the current node with the the top of the P stack
• in both cases all nodes that are part of a SCC are tracked in a stack in the visited order starting from the head. In the path-based approach, this is the S stack

For the steps of the algorithm you can refer to the linked Wikipedia page. You can find my implementation of findStronglyConnectedComponentsPathBased on my Gist along with some tests in PathBasedSCCJTests.