UVa10129 Play on Words


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

UVa10129 Play on Words

サイト

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

解説

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

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

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

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