Pointer Loop Length
next_node describes len(next_node) nodes numbered from 0: exactly one arrow leaves node i, and it points at node next_node[i], which may be i itself. Several arrows may point at the same node, and some nodes may have no arrow pointing at them.
Start at node start and follow the arrows without stopping. Because every node has exactly one arrow out, you eventually keep going around the same loop of nodes. Return the number of nodes on that loop. A node whose arrow points at itself forms a loop of 1.
Example 1
The walk goes 0, 1, 2, 0, ... so the loop has three nodes.
Example 2
The walk goes 0, 1, 2, 3, 1, 2, 3, ...: node 0 is only passed once, and the loop 1, 2, 3 has three nodes.
Constraints
1 <= len(next_node) <= 500 <= next_node[i] <= len(next_node) - 10 <= start <= len(next_node) - 1
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Rumour DaysEasy
- Same Network QueriesEasy
- Tunnels to Every StationEasy
- Blocks to the Nearest ShopMedium
- Build Order ExistsMedium
- Calm SquaresMedium
- Cheapest Toll TripMedium
- Connect All OfficesMedium