[addaon]

Fair enough. I imagine a simple (but O(cycles) space, not O(1)) way to do this is to still tortoise-and-hare, and on detecting a cycle, break the link behind you (by recording it in a table) and continue the BFS. If O(cycles) = O(n) this isn't terribly interesting compared to other approaches, but if O(cycles) < O(n) it might be helpful.

[addaon]

Actually, now that I spend more than ten seconds thinking about this, I think this requires O(1) space; you only need to remember the single most recent link behind you to avoid following it again. Remembering a single break is sufficient to get you to either the next cycle or (if no more) terminate the BFS; and once you detect the next cycle you can safely remember only /its/ break since BFS will never take you back to the first cycle. Assuming streaming output (e.g. print identification of each cycle as you detect it -- including e.g. printing each node until you see the break point, which will identify each node that is part of the cycle), this is O(n) time and O(1) space, which I believe is optimal.