AOJ 0225 Kobutanukitsuneko

有向グラフが与えられるのでそれがオイラーグラフかどうか判定する問題。
無向の時はすべての頂点が偶数であればいいが有向グラフのときはすべての頂点で入次数と出次数が等しければ良いらしい。この際まとめておくと

• 無向グラフがオイラー閉路を持つ　⇔　すべての頂点の次数が偶数
• 無向グラフがオイラー路を持つ　　⇔　次数が奇数の頂点が丁度2つ
• 有向グラフがオイラー閉路を持つ　⇔　すべての頂点の入次数と出次数が等しい
• 有向グラフがオイラー路を持つ　　⇔　出次数が入次数より1多い頂点が1つ、入次数が出次数より1多い頂点が1つ、残りの頂点の出次数と入次数が等しい

ただしこれらは頂点が連結なときにしか成り立たない。なのでUnionFindかなにかで連結かどうかも判定する

int n;
int in[30],out[30];
struct UnionFind
{
	int par[30],rank[30];
	void init()
	{
		for(int i=0;i<30;i++)
		{
			par[i]=i;
			rank[i]=0;
		}
	}
	int find(int x)
	{
		if(x==par[x])return x;
		else return par[x]=find(par[x]);
	}
	void unite(int a,int b)
	{
		a=find(a);
		b=find(b);
		if(rank[a]<rank[b])par[a]=b;
		else
		{
			par[b]=a;
			if(rank[a]==rank[b])rank[a]++;
		}
	}
	bool same(int a,int b)
	{
		return find(a)==find(b);
	}
};
int main()
{
	while(1)
	{
		UnionFind uf;
		uf.init();
		memset(in,0,sizeof(in));
		memset(out,0,sizeof(out));
		scanf("%d",&n);
		if(n==0)break;
		for(int i=0;i<n;i++)
		{
			string s;
			cin >> s;
			uf.unite(s[0]-'a',s[s.size()-1]-'a');
			out[s[0]-'a']++;
			in[s[s.size()-1]-'a']++;
		}
		int k;
		for(int i=0;i<30;i++)
		{
			if(in[i]==0&&out[i]==0)continue;
			k=uf.find(i);
			break;
		}
		for(int i=0;i<30;i++)
		{
			if(in[i]==0&&out[i]==0)continue;
			if(uf.find(i)!=k)
			{
				printf("NG\n");
				goto end;
			}
		}
		for(int i=0;i<30;i++)
		{
			if(in[i]!=out[i])
			{
				printf("NG\n");
				goto end;
			}
		}
		printf("OK\n");
		end:;
	}
	return 0;
}