Question 1275

One Exit Per Room

A game world has 200,000 rooms. Every room has exactly one exit, given by an array next[1..200000] where next[i] is the room you arrive in. For each of 50,000 queries you are given a starting room and asked where you land after exactly 10910^9 steps.

Which statement about this graph is guaranteed, and what does it buy you?

A

It is strongly connected, because following exits from any room eventually reaches every other room.

B

Every vertex has out-degree 1, so walking from any room must eventually revisit a room. Each component is a set of trees feeding into exactly one cycle, so you find the tail length and the cycle length once and finish with a modulo.

C

It is a DAG: the exits define a strict ordering, so one topological pass answers every query.

D

It is a forest of trees rooted at the rooms that have no exit, so each query is a walk up to the root.