Tarjan's algorithm to determine wheter a directed graph has a cycle

Question

I want to know if a directed graph has a cycle; something like

1->2->3->2 ...
1->2->3->4->3...
1->1->1->1...

So, I'm considering the Tarjan's strongly connected algorithm.

Do you think that with this algorithm I'll be able to know if some directed graph has a cycle?

Thanks!

Answer 1

A slight modification to Tarjan's algorithm will serve you well. Run it as normal, but modify the DFS routine to return True if a node is visited more than once.

Equivalently, return True as soon as you find a strongly connected component with more than one cycle.