UVa10129 Play on Words

UVa10129 Play on Words

サイト

http://uva.onlinejudge.org/external/101/10129.html

解説

与えられた各文字列の先頭から末尾に有向グラフを張り、オイラー路を作れるか確認する。

頂点に入るとき+1 頂点から出るとき-1 各頂点の相対次数を0を確かめる。

ただしグラフは閉路でない場合もあるので、しりとりのはじめの文字と最後の文字の相対次数が0とならない場合がある。

オイラー路の問題では、考えているグラフが連結である必要があるのでDFSをかける

最終更新:2013年10月20日 11:25