Graph Theory37 sections · 1633 units
Open in Course

CSES 1197 Cycle Finding - Finding Cycle Start

(Inside the cycle)

If node vv improved in the nn-th iteration, it is affected by a negative cycle, but it might not be inside the cycle itself. It could be a node reachable from the cycle. Walk back nn steps from vv using parent pointers. After nn steps, you are guaranteed to be at a node inside the cycle. Why?

Because nn edges in a graph with nn nodes must include a repeated node. From there, follow parents and record nodes until you see a repeated node. That gives you the cycle. The first repeated node is where the cycle begins and ends.