AOJ 0225 （Kobutanukitsuneko : こぶたぬきつねこ）

【問題】

https://onlinejudge.u-aizu.ac.jp/problems/0225

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0225

【解説】

単語のしりとりが循環可能かどうかを判定する問題。しりとりなので文字列の先頭と末尾の文字以外については関係ない。そのため各単語は、先頭の文字ノードから末尾の文字ノードへの遷移のオートマトンとみなすことができるため、この問題はグラフに置き換えて考えることができ、循環可能かということは、そのグラフがオイラーグラフ（各頂点を一度ずつ通り、始点に戻ることができる）かどうかということである。

オイラーグラフということは、すなわち全てのグラフの入る辺の数と出る辺の数が同数であることが条件となるため、a～zまでの入る辺と出る辺の数を管理し、それらが同数であることを確かめればよい。

また、前提として、グラフが連結であることが前提である。これはUnionFind木を用いて、全ての親が同一であるかを判定することで確かめることができる。

【コード】