TopCoder, SRM 666, Division 2, Level 1 : DevuAndGame

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13744&rd=16515

問題概要

　全ての頂点の出次数が高々 1 であるような，$N$ 頂点の有向グラフが与えられる．このグラフにおいて頂点 0 から辺に沿って移動したとき，出次数 0 の頂点に到達可能か？

• $1 \leq N \leq 50$

解法

　頂点 0 から始めて，1 歩ずつ進めていくことを考えます．
　今，ある頂点にいるとします．その頂点がゴール（出次数 0 の頂点）ならば，到達可能であるとして終了できます．逆に，ゴールに到達していないならば現在の頂点の出次数は 1 です．出次数 1 なら次の移動先が一意に定まるので，現在位置を更新できます．
　ゴールに到達可能なケースならこれで十分ですが，これではゴール不可能なことを検出できません．ゴールに到達できない場合はどのようなケースか考えてみると，閉路に入ってしまった場合です．閉路を回ったときに限り，同じ頂点を複数回通ることになるので，各頂点に対して visited かどうかを覚えておけば，閉路に入ったこと（＝ゴールできないこと）を検出できます．
　この解法は，各頂点を高々 1 回訪問し，各頂点からの移動先は $O( 1 )$ で求まるので全体で $O( N )$ 時間です．

コード

template < typename T = int > using VT = vector< T >;

#define SZ( v ) ( (int)( v ).size() )

class DevuAndGame
{
public:
	string canWin( vector <int> nextLevel )
	{
		int N = SZ( nextLevel );

		VT< bool > visited( N );
		int current = 0;

		for ( ; current != -1; current = nextLevel[ current ] )
		{
			if ( visited[ current ] )
			{
				return "Lose";
			}
			visited[ current ] = true;
		}
		return "Win";
	}
};