Problem 0225 : Kobutanukitsuneko

問題概要

日本語なので本文参照(http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0225&lang=jp

与えられた英小文字からなる単語を使い、しりとりをする。
与えられた単語全てを1度ずつ使い、かつ、しりとりの一番最初の単語の最初の文字と、しりとりの一番最後の単語の最後の文字を一致させることができるかを判定せよ。

解法

26個のアルファベットに、26個の頂点を対応させたグラフを考える。
単語の先頭の文字の頂点から、単語の末尾の文字の頂点へ枝を張ると、
問題はこのグラフにオイラー閉路が存在するかどうかを問うていることになる。


したがって、各頂点の相対字数が0かつグラフが連結であるかどうかを判定すればいい。
連結の判定にはdfsを用いた。
この際、使われてないアルファベットのノードは探索や判定に含めないことに注意する。

ソースコード

char in[33];
int n,deg[26];
bool v[26];
vi e[26];

void dfs(int c){
  v[c]=1;
  fr(i,e[c])if(!v[*i])dfs(*i);
}
int main()
{
  while(scanf("%d",&n),n){
    rep(i,26)e[i].clear(),deg[i]=0,v[i]=1;
    int a,b;
    rep(i,n){
      scanf("%s",in);
      a=in[0]-'a'; b=in[strlen(in)-1]-'a';
      e[a].pb(b);
      deg[a]++; deg[b]--; v[a]=v[b]=0;
    }
    dfs(a);
    rep(i,26)if(!v[i]||deg[i]!=0){
      puts("NG"); goto END;
    }
    puts("OK"); END:;
  }
  return 0;
}