3 ms·
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 ze
by toxik 7y ago
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 7y agoThat is not enough, since you may still get stuck in a loop.
- toxik 7y agoFair point, but that is inevitable unless it's a game where the user cannot go back, very few games would fit that bill then.
- deleted 7y ago[deleted]