AtCoder Grand Contest 027 C 「ABland Yard」

問題文

C - ABland Yard

 

手でいくつか例を試すと、「AABBというループを含んでいる」ことと「A,Bからなる任意の文字列を作れる」ことが同値であることがわかる。

(証明)

「AABBというサイクルを含んでいる」⇒「A,Bからなる任意の文字列を作れる」は簡単で、サイクル内のどの頂点からでもA,Bに行けるので適当にやると任意の文字列が作れる。

「A,Bからなる任意の文字列を作れる」⇒「AABBというサイクルを含んでいる」は、任意の文字列が作れるならとくにAABBAABBAABB...を作ることが出来るということからわかる。

 

具体的な判定方法としては「頂点を倍にする」テクがある。Aの頂点はAABBの奇数番目のAとして用いられるか、偶数番目のAとして用いられるかのどちらかなので、それぞれの状況に対応する頂点を作って有向辺を張り、その有向グラフがDAGかどうかを判定すればよい。