Cycle Detection

Different graph kinds need different tests. Using the undirected test on a directed graph (or vice versa) is a classic source of wrong answers.

Undirected: DFS with a parent

A back edge to any visited vertex that is not the parent closes a cycle.

bool dfs(int u, int p) {
    visited[u] = true;
    for (int v : adj[u]) {
        if (v == p) { p = -1; continue; }   // skip the edge we came from, once
        if (visited[v]) return true;        // back edge -> cycle
        if (dfs(v, u)) return true;
    }
    return false;
}

Parallel edges and self-loops

Skipping every occurrence of the parent misses the 2-cycle formed by parallel edges. Skip it once (as above), or track edge ids instead of vertex ids. A self-loop is a cycle by itself.

Alternatively, with DSU: process edges; if both endpoints are already in the same set, that edge closes a cycle. This is also how Kruskal avoids cycles.

Simplest test of all: an undirected graph is acyclic iff it is a forest, iff $m=n-c$ where $c$ is the number of components.

Directed: three colours

vector<int> state;   // 0 = white (unvisited), 1 = grey (on stack), 2 = black (done)
 
bool dfs(int u) {
    state[u] = 1;
    for (int v : adj[u]) {
        if (state[v] == 1) return true;          // back edge -> cycle
        if (state[v] == 0 && dfs(v)) return true;
    }
    state[u] = 2;
    return false;
}

A grey neighbour means an ancestor on the current DFS path — a genuine cycle. A black neighbour is a forward or cross edge and is harmless. Only checking “visited” (merging grey and black) reports false cycles.

Equivalent tests:

• Kahn’s algorithm outputs fewer than $n$ vertices.
• Some SCC has size $>1$, or a single vertex has a self-loop.

Recovering the cycle

Keep a parent array and, on finding the back edge $u\to v$, walk parents from $u$ back to $v$:

vector<int> cyc;
for (int x = u; x != v; x = par[x]) cyc.push_back(x);
cyc.push_back(v);
reverse(cyc.begin(), cyc.end());

Functional graphs

When every vertex has out-degree exactly 1 (next[v]), the graph is a functional graph: each component is a “rho” — a tail leading into exactly one cycle. This structure appears constantly (permutations, “next pointer” problems, iterated functions).

Task	Method
Find the cycle from a start vertex	Floyd or Brent, $O(\mu +\lambda )$ time, $O(1)$ space
Find all cycles	colour DFS, or repeated walking with visit timestamps
$k$-th successor	binary lifting, $O(\log k)$
Cycle lengths	one pass, marking the step index at which each vertex was seen

A permutation is a functional graph with in-degree 1 as well, so it decomposes entirely into disjoint cycles — the basis of permutation order, parity, and cycle-sorting arguments.

Negative cycles

A different question entirely: not “is there a cycle” but “is there a cycle of negative total weight”. That needs Bellman-Ford or Floyd-Warshall — see Negative Cycles.

See also: DFS · Topological Sort · Floyd’s Cycle Detection