Lesson 23.3 · Cycle Detection
One Outgoing Edge: Functional Graphs
When every node points to at most one next node, each walk is a path that ends or falls into exactly one cycle. Timestamps find cycle lengths in O(n).
8 min
Think of it like this
A treasure hunt where each clue points to exactly one next location. Follow the clues and you either finish or start going round a loop. That's the linked-list cycle problem with many starting points.
1.Timestamps per walk
Give each node the time you first stepped on it. Start a walk from every unvisited node, remembering the walk's start time. If the walk hits a node whose time is ≥ the start time, it was stepped on during this walk, and the cycle length is current time − that node's time. Nodes from earlier walks are skipped, so the total work is O(n).
Remember
- Each node has ≤ 1 successor.
- Timestamps distinguish this walk from earlier ones.
- O(n) total.
Common mistakes
- Restarting a fresh visited set for each start (O(n²)).