FunctionRacerProblemsRace

Calm Squares

MediumGraphsPython, JavaScript, TypeScript, Java, C++

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

moves [[1,3],[2],[],[3]]
returns [1,2]

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

moves [[1,2],[2],[0],[]]
returns [3]

Squares 0, 1 and 2 chase each other in a circle; only the stuck square 3 is calm.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems