CSES 1197 Cycle Finding - Walkthrough

Graph: $1 o 2$ ($-1$), $2 o 3$ ($-2$), $3 o 1$ ($-3$), $4 o 1$ ($1$). Run Bellman-Ford from node $1$. After $3$ iterations, dist[1] = -6, dist[2] = -1, dist[3] = -3. The $4$-th iteration improves dist[2] (to $-7$) via edge $1 o 2$. Set parent[2] = 1.

Walk back $4$ steps from node $2$: $2 leftarrow 1 leftarrow 3 leftarrow 2 leftarrow 1$. After $4$ steps, you are at node $1$ (inside the cycle). Follow parents from $1$: $1 leftarrow 3 leftarrow 2 leftarrow 1$. Reverse to get forward cycle $1 o 2 o 3 o 1$. Output: $1 2 3$.