CSES 1197 Cycle Finding - Implementation

Here is the solution:

dist := [0] * (n + 1)
parent := [-1] * (n + 1)
for round from 1 to n - 1
    for (u, v, w) in edges
        if dist[u] + w < dist[v] then
            dist[v] := dist[u] + w
            parent[v] := u

// Find node in cycle
cycle_node := -1
for (u, v, w) in edges
    if dist[u] + w < dist[v] then
        cycle_node := v
        break

// Trace back to find cycle
if cycle_node != -1 then
    for i from 1 to n
        cycle_node := parent[cycle_node]
    // Now trace the cycle
    current := cycle_node
    cycle := []
    repeat
        cycle.append(current)
        current := parent[current]
    until current = cycle_node
    cycle.reverse()
    print cycle

The double-walk guarantees correct cycle extraction even when the improved node is outside the cycle.

This runs in $O(VE)$ time and uses $O(V)$ space.