Undirected
Only tree edges + back edges. Back edges reveal cycles. Foundation of bridges + articulation-point algorithms.
Advertisement
Directed
All four types. Back edge = cycle. Presence of any back edge = graph has cycle.
Advertisement
Detection
Track color: WHITE (unvisited), GRAY (in stack), BLACK (finished). Edge to GRAY = back. Edge to BLACK with disc[v] > disc[u] = forward, else cross.
Complexity
O(V+E). Single DFS.