しりとり
(paizaランク A 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
整数 n と、n 個の文字列 s_1, s_2, ..., s_n が与えられます。
これらすべての文字列をちょうど 1 回ずつ使用して、しりとりをすることができるかどうか判定してください。
厳密には、{1, 2, ..., n} の順列 σ = (σ_1, σ_2, ..., σ_n) であって、last(s_{σ_i}) = first(s_{σ_{i + 1}}) (1 ≦ i ≦ n - 1) を満たすものが存在するかどうか判定してください。
ただし、26 個の英小文字を頂点とし、各文字列 s_i を頂点 first(s_i) から頂点 last(s_i) へ向かう辺としてみたとき、 入次数、出次数がともに 0 の頂点を除くとこの有向グラフが弱連結であることが保証されます。つまり、しりとりをすることができるかどうかの判定をするために、準オイラーグラフかどうかの判定をすれば良いということです。
ただし、first(x) := x_1, last(x) := x_{|x|}, とします。つまり、first(x) は (x の最初の文字), last(x) は (x の最後の文字) を表します。
- 入力される値
-
n
s_1
...
s_n
・ 1 行目に、文字列の個数を表す整数 n が与えられます。
・ 続く n 行では、文字列 s_i が与えられます。(1 ≦ i ≦ n)
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
与えられたすべての文字列をちょうど 1 回ずつ使用して、しりとりをすることができる場合は 1, そうでない場合は 0 を出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ n は整数
・ 1 ≦ n ≦ 100
・ s_i は英小文字からなる文字列
・ 1 ≦ |s_i| ≦ 100
・ 入力をグラフとしてみたとき、入次数、出次数がともに 0 の頂点を除くと弱連結である
- 入力例1
-
6
apple
clang
csharp
erlang
gcc
paiza
- 出力例1
-
1
- 入力例2
-
6
apple
clang
csharp
gcc
paiza
python
- 出力例2
-
0
