complexitydsagraphs
How can DFS detect a directed cycle?
Anonymous
Track each node as unseen, active, or done during DFS. An edge to an active node means a cycle; edges to done nodes do not. With adjacency lists, the traversal takes O(V + E) time and O(V) extra space.
0