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