しりとりできるかできないか

はじめに

スキルチェックのコードは載せることができないので問題集のコードと考え方をまとめてみます。

問題

整数 n と、n 個の文字列 s_1, s_2, ..., s_n が与えられます。
これらすべての文字列をちょうど 1 回ずつ使用して、しりとりをすることができるかどうか判定してください。
という問題でスキルチェックでは　A に相当する問題です。

考え方

まずは各文字列を頂点から頂点へ向かう辺として考え、準オイラーグラフであるかを判別します。

準オイラーグラフ

ある頂点から始めてすべての辺を一筆書きして最初の頂点に戻ってくることが可能なグラフをオイラーグラフといいます。
　その上で一筆書きで全ての辺を通りつつ最初の頂点に戻ってこなくても良いグラフを準オイラーグラフといいます。

入次数、出次数を表す配列 indegree, outdegree を 0 で初期化
　入力を受け取り、変数 s に代入
　
　outdegree[s[0]], indegree[s[- 1]] に 1 を足す。
　(入次数) == (出次数 + 1), (入次数 + 1) == (出次数), (入次数) == (出次数) となる頂点の個数をそれぞれ変数 startCount, goalCount, midCount に記録
　startCount == goalCount == 0 かつ midCount == 26 であれば 1 を出力
　startCount == goalCount == 1 かつ midCount == 26 - 2 であれば 1 を出力
　それ以外であれば 0 を出力

コード

n = gets.to_i
s = []

start_count = 0
goal_count = 0
mid_count = 0

indegree = Hash.new(0)
outdegree = Hash.new(0)

('a'..'z').each do |c|
  indegree[c] = 0
  outdegree[c] = 0
end

n.times do
  input = gets.chomp
  s << input

  outdegree[input[0]] += 1
  indegree[input[-1]] += 1
end

('a'..'z').each do |c|
  start_count += 1 if indegree[c] == outdegree[c] + 1
  goal_count += 1 if indegree[c] + 1 == outdegree[c]
  mid_count += 1 if indegree[c] == outdegree[c]
end

if start_count == 0 && goal_count == 0 && mid_count == 26
  puts 1
elsif start_count == 1 && goal_count == 1 && mid_count == 24
  puts 1
else
  puts 0
end