---
title: "Cycles: Detection, Extraction, Feedback Sets"
summary: Find one cycle in linear time, find the shortest one, and know what "remove the fewest vertices to make it a DAG" costs.
difficulty: core
tags: [cycles, DFS, NP-complete]
time: n + m
see: [directed/dag-toposort, complexity/escape]
---

:::definition label="Three cycle questions, three complexities"
- *Does a cycle exist?* $O(n+m)$ — DFS back edge, or Kahn's leftovers.
- *Output one cycle?* $O(n+m)$ — keep parents, walk back.
- *Shortest cycle (girth)?* $O(nm)$ — BFS from every vertex; $O(n^\omega)$ for dense unweighted.
- *Longest cycle / Hamilton?* NP-complete (@euler/hamilton-dp for $O(2^n n^2)$).
- *Fewest vertices hitting all cycles (feedback vertex set)?* NP-hard, FPT, $O(4^k k n m)$ by bounded search tree.
:::

## Extracting a cycle from DFS
```cpp find-cycle.cpp
vector<int> col(n), par(n, -1), cycle;
bool dfs(int u) {
    col[u] = 1;
    for (int v : g[u]) {
        if (col[v] == 1) {                              // back edge u -> v
            cycle.push_back(u);
            for (int x = par[u]; x != v && x != -1; x = par[x]) cycle.push_back(x);
            cycle.push_back(v);
            return true;
        }
        if (!col[v]) { par[v] = u; if (dfs(v)) return true; }
    }
    col[u] = 2;
    return false;
}
```
The invariant that makes this correct: `col[u] == 1` means "$u$ is on the current recursion path", so the path $\operatorname{par}$-chain from $u$ back to $v$ plus the edge $u \to v$ is a directed cycle (@trees/dfs, edge classification).

## Shortest cycle through BFS
For unweighted digraphs, run BFS from each $s$ and check every edge $u \to v$ where $v$ is an ancestor-side vertex: the answer is $\min(\operatorname{dist}[u] + 1)$ over edges closing a loop to $s$; total $O(nm)$. For undirected girth, BFS with parent-tracking from each vertex finds it in the same time (careful: parallel edges and self-loops need their own check, since the "parent exclusion" hides them).

:::example title="Shortest cycle in an unweighted undirected graph, one BFS per vertex"
Stop expanding when you meet an already-visited vertex that is *not* your parent: candidate length $= d[u] + d[v] + 1$. With $n \le 2000$ that is $4 \times 10^6$ per… $O(nm)$ total, and it also gives the **odd** girth if you keep two copies of each vertex (parity-layered graph) — the standard trick for "shortest odd cycle".
:::

## Feedback: what "almost a DAG" buys you
:::idea title="Small feedback set = DP on a DAG with a bag"
If $k$ vertices hit every cycle, the remaining graph is a DAG. Then many NP-hard problems become $O(2^k \cdot \operatorname{poly}(n))$: enumerate the state of the $k$ special vertices, DP along the DAG order for the rest. Recognising this pattern — "the input is a DAG plus a few extra edges" — is a whole solution, not a hint.
:::

:::theorem title="DAG + one edge"
Adding a single edge $xy$ to a DAG creates exactly the cycles through $xy$: the number of new cycles is the number of paths $y \leadsto x$ (computable by one DAG DP, @directed/dag-toposort).
:::

:::proof
Every new cycle must use the new edge; removing $xy$ from it leaves a directed path from $y$ to $x$ in the original DAG, and the correspondence is bijective. ∎
:::

That one-line argument is the core of "count cycles after adding edges" problems and of the incremental-DAG trick used in transitive-closure updates.

:::problems
- [[CSES 1678]] Round Trip II | https://cses.fi/problemset/task/1678 | core | directed cycle output
- [[CSES 1757]] Course Schedule II | https://cses.fi/problemset/task/1757 | core | print the cycle
- [[CF 977E]] Cyclic Components | https://codeforces.com/problemset/problem/977/E | core | which components are pure cycles
- [[CSES 2138]] Reachable Nodes | https://cses.fi/problemset/task/2138 | hard | DAG reachability, bitsets
:::