Concurrent algorithm for strongly connected components (SCCs)
This answer might come late, but there's a work by Gavin Lowe: "Concurrent Depth-First Search Algorithms", Proceedings of TACAS 2014, p. 202--216, Volume 8413 of LNCS, Springer that has descriptions for parallel algorithms for computing strongly connected components, lasso-shaped paths and finding nodes that are part of a cycle.