[toxik]

More precisely, construct a graph with vertices (u, v) where u is a prior state and v a possible successor state, then there must not be a node of out-degree zero unless it is an end state.

As far as complexity goes, this should be linear in number of vertices. In fact, you don't even really have to construct the graph, just count out degree.

[akrasuski1]

That is not enough, since you may still get stuck in a loop.

[toxik]

Fair point, but that is inevitable unless it's a game where the user cannot go back, very few games would fit that bill then.