Nodes on Cycles — Solution & Editorial

Back to the Problem

A functional graph is 'rho-shaped' per component. Walk from each unvisited node marking a gray path; when you re-hit a gray node, the tail from that node is a cycle. Iterative to avoid recursion limits.

Complexity: O(N)

Watch out: Self-loops (a_i = i) are cycles of length 1.