Calm Squares
A board has squares numbered 0 to len(moves) - 1. From square i a token may move to any square listed in moves[i]; an empty list means the token is stuck there and play ends. A list may repeat a square, and a square may list itself.
A square is calm when every possible sequence of moves that starts there ends after finitely many moves, that is, no choice of moves can keep the token moving forever. Return the calm squares in increasing order. Return [] if no square is calm.
Example 1
Square 3 moves to itself forever, so 3 is not calm and neither is 0, which can move to 3. Squares 1 and 2 always end at 2.
Example 2
Squares 0, 1 and 2 chase each other in a circle; only the stuck square 3 is calm.
Constraints
1 <= len(moves) <= 500 <= moves[i][j] < len(moves)- At most 100 entries in total
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Cheapest Toll TripMedium
- Connect All OfficesMedium
- Count the Shortest RoutesMedium
- Forced SidesMedium
- Largest PatchMedium
- Longest TrailMedium
- Lowest High PassMedium
- Mutual Reach GroupsMedium