POJ 1386 Play on Words

問題

単語のリストが与えられる。
このリストの単語を使ってしりとりをする。

与えられた単語を、全てちょうど1度ずつ使うしりとりができるかどうかを判定せよ。

制約条件

単語の数≦100000

方針

'a'から'z'までの文字を頂点とするグラフを考える。
各単語について、先頭の文字の頂点から終端の文字の頂点まで、有向の枝を張る。

すると、単語をちょうど1度ずつ使うしりとりというのは、このグラフ上におけるオイラー歩（全ての辺を一度ずつ通るようなパス）に相当する。
有向グラフがオイラー歩をもつかは、グラフが連結かつ各頂点の相対次数（入次数-出次数）が、

• +1がひとつ、-1がひとつ
• すべて0

のどちらかが成り立つことが必要十分である。

（必要性は明らかで、逆も無向オイラー歩の条件の証明と同じように考えればわかる）

ソースコード

int n;
char str[1001];
int g[26][26], deg[26];
bool v[26];

void dfs(int c){
  v[c]=1;
  rep(i,26)if(g[c][i]&&!v[i])dfs(i);
}

int main(){
  int T; scanf("%d",&T);
  while(T--){
    scanf("%d",&n);
    rep(i,26)v[i]=1, deg[i]=0;
    
    rep(i,n){
      scanf("%s",str);
      char a=str[0], b=str[strlen(str)-1];
      v[a-'a']=v[b-'a']=0;
      g[a-'a'][b-'a']=1;
      deg[a-'a']++; deg[b-'a']--;
    }
    
    int s=-1, t=-1;
    rep(i,26){
      if(deg[i]==1){
        if(s==-1)s=i;
        else s=-2;
      }
      else if(deg[i]==-1){
        if(t==-1)t=i;
        else t=-2;
      }
      else if(deg[i]!=0){
        s=t=-2;
      }
    }
    if(s==-2)goto FAIL;
    if(s==-1){
      rep(i,26)if(!v[i])s=i;
    }
    
    dfs(s);
    rep(i,26)if(!v[i])goto FAIL;
    
    puts("Ordering is possible."); continue;
    FAIL:puts("The door cannot be opened.");
  }
  return 0;
}