CSES 1197 Cycle Finding - Parent Tracking

When you relax an edge $u \to v$, store parent[v] = u. This lets you trace back the path that created the current distance. Parent pointers form a tree of shortest paths from the source. If the $n$-th iteration improves distance to node $v$, you know $v$ is affected by a negative cycle.

Trace back from $v$ using parent pointers to find the cycle. After tracing back $n$ steps, you are guaranteed to be inside the cycle. This is because any path longer than $n-1$ edges must contain a repeated node, which forms a cycle.