edge classification
When depth-first search runs, it carves the graph into a DFS tree of discovery edges plus all the leftover edges. The beautiful thing is that those leftover edges are not random clutter — each one falls into a small number of well-defined types depending on how its endpoints sit in the tree, and knowing the type of an edge tells you something concrete about the graph's structure. Edge classification is the labelling of every edge as it is encountered, and it is the diagnostic readout DFS produces almost for free.
Using discovery and finish timestamps, here is how to classify an edge (u, v) the moment DFS examines it from u. If v is unvisited, it becomes a tree edge (the edge used to discover v). If v is already visited but still 'on the stack' — an ancestor of u whose interval contains u's — it is a back edge, pointing from a descendant up to an ancestor. If v is already finished and is a descendant of u (v's interval is nested inside u's, but v was reached earlier by another route), it is a forward edge. If v is already finished and is neither ancestor nor descendant (the intervals are disjoint), it is a cross edge, jumping between two separate branches. You can decide which case you are in purely from the timestamps and a 'still on stack' flag, so classification adds no asymptotic cost: it stays O(n + m).
These labels are the raw material for the rest of this field. A back edge is exactly a witness of a cycle, so 'is there a back edge?' is cycle detection. In a directed acyclic graph there are no back edges by definition, which is what makes topological sort possible. Forward and cross edges only appear in directed DFS (undirected DFS produces only tree and back edges). The honest caveat to remember: the classification is relative to one particular DFS run — a different start vertex or neighbour order can turn what was a cross edge into a forward edge. What is invariant and trustworthy is the presence or absence of a back edge, since that reflects a real cycle in the graph, independent of how you searched.
Directed graph a->b, b->c, a->c, c->a. DFS from a discovers a->b (tree), b->c (tree), then from c the edge c->a sees a still on the stack: back edge (a cycle a-b-c-a). Later from a the edge a->c sees c already finished and nested inside a: forward edge. No cross edge appears here.
Timestamps plus an on-stack flag decide each edge's type; a back edge is the unmistakable mark of a cycle.
Undirected DFS only ever produces tree and back edges — forward and cross edges are a directed-graph phenomenon. And the labels are relative to one DFS run; only the existence of a back edge (a real cycle) is run-independent.