AOJ : 0225 - Kobutanukitsuneko

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0225&lang=jp
日本語なので省略です

アルゴリズム

この問題は簡潔にいうと, 「入力された多重辺もループも許す有向グラフが, オイラーグラフであるかを求める問題」です.

しりとりにおいて肝心なのは, 単語の最初の文字と最後の文字だけです.
そのため, この各単語の最初の文字と最後の文字をノードとみなし, そのノード同士をつなげて, グラフを作成します.

グラフ作成後の解き方はいたって簡単です.
しりとりで, 最初に使った単語の頭文字に戻ってくるわけですから, 作成したグラフがオイラーグラフであるかの確認を行えばいいです.
有向グラフにおいては, 「各ノードにおける入次数と出次数が一致している」ならば, そのグラフはオイラーグラフになります.
ただし, この法則は, グラフが連結でなければ成り立たないので, オイラーグラフの判定前にグラフが連結であるか確認しておく必要があります.

プログラム

#include <iostream>
#include <set>
#include <cstring>
using namespace std;

int t[26][26];

//ノードidからいくつのノードに移動可能か
//すでに探索済みのノードは通らない
int reachableNode(int id,bool *used){
  int res = 1;

  used[id] = true;
  for(int i=0;i<26;i++){
    if(t[id][i] > 0 && !used[i]){
      res += reachableNode(i,used);
    }
  }

  return res;
}

int main(void){
  int n;

  while(cin>>n && n){
    string s;
    int from,to;
    set<int> ap;

    memset(t,0,sizeof(t));

    for(int i=0;i<n;i++){
      cin>>s;
      from = s[0] - 'a';
      to = s[s.length()-1] - 'a';

      //自己ループ以外の辺はカウント
      if(from != to){
        t[from][to]++;
      }
      ap.insert(from);
      ap.insert(to);
    }

    //森が一つだけであるかの確認
    bool used[26];
    memset(used,0,sizeof(used));
    int count = reachableNode(from,used);
    if(count != ap.size()){
      cout<<"NG\n";
      continue;
    }

    //入次数と出次数が同じかどうかの確認
    set<int>::iterator i = ap.begin();
    for(;i!=ap.end();i++){
      int in=0,out=0;
      for(int j=0;j<26;j++){
        in += t[j][*i];
        out += t[*i][j];
      }

      if(in != out) break;
    }

    if(i == ap.end())
      cout<<"OK\n";
    else
      cout<<"NG\n";
  }

  return 0;
}