torus711 のアレ

主に競技プログラミングの問題について書きます

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

問題概要

 全ての頂点の出次数が高々 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";
	}
};