Which cycle detection within a directed graph are more efficient than O(n^2)?
algorithm, directed-graph, graph-theory
Solution
Tarjan's strongly connected components algorithm has `O(|E| + |V|)` time complexity.
For other algorithms, see Strongly connected components on Wikipedia.
Problem
Is there an algorithm that is more time efficient than O(n^2) for detecting cycles within a directed graph? I have a directed graph representing a schedule of jobs that need to be executed, a job being a node and a dependency being an edge. I need to detect the error case of a cycle within this graph leading to cyclic dependencies.