ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 0225 Kobutanukitsuneko

問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0225


・概要
複数の文字列が与えられる。
それらをしりとりのような感じで全部繋げ、かつ最初の文字列の先頭と最後の文字列の後尾を繋げることができるか(オイラー閉路が存在するか)を判定する問題です。


・解法
オイラー路に関する知識とDFS(深さ優先探索)を用いて解くことができます。

まずオイラー路が存在する条件ですが、
各ノードにおける入ってくる数と出ていく数が一致すればよいです。(説明下手)

文字列は小文字のみで与えれらるのでa~zの26つ分の配列を準備しておきます。

あとは入力される文字列の先頭・後尾のアルファベットに対して処理をしてあげます。

あとは閉路になっているかどうか(あるノードから出発して、一筆書きで最初のノードに戻ってこれるかどうか)をDFS1回で確かめればよいです。


ソースコード

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

#define rep(i,n) for(int i = 0 ; i < (int)(n) ; i++)

int in[26],out[26];
int path[26][26];
bool visited[26];

void dfs(int pos){
   visited[pos] = true;
   
   rep(j,26){
      if(path[pos][j]==1 && !visited[j])dfs(j);
   }
}

int main(){
   int n;
   while(cin >> n){
      if(n==0)break;
      
      memset(in,0,sizeof(in));
      memset(out,0,sizeof(out));
      memset(path,0,sizeof(path));
      memset(visited,true,sizeof(visited));

      string s;
      rep(i,n){
	 cin >> s;
	 int from = s[0] - 'a';
	 int to = s[s.size()-1] - 'a';
	 in[from]++;
	 out[to]++;
	 path[from][to] = 1;
	 visited[from] = visited[from] = false;
      }
      
      bool check = true;
      rep(i,26){
	 if(in[i]!=out[i])check = false;
      }
      
      if(check){
	 dfs(s[0]-'a');
	 rep(i,26){
	    if(!visited[i])check = false;
	 }
      }

      cout << (check ? "OK" : "NG") << endl;
   }
   return 0;
}