UVa 10129 Play on Words

题目：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=105&page=show_problem&problem=1070

题目大意是给你一串单词，判断能否连接成一条长串，两个单词能够连接的条件是后一个单词的首字母与前一个单词的尾字母相同（单词至少有2个字母）。单词仅由小写字母组成。

这个题目对于我们新手来说还是有难度的。首先这是一个图论问题，我们把单词看作是点，单词之间的连接关系看作是边。题目所给的数据规模：单词的个数到达10万，所以我们不能把每一个单词看作一个点，而是把相同的单词看左是一个点。实际上，对于每一个单词，我们只需要知道它的首字母和尾字母就可以了，中间并不管，那么首字母和尾字母相同就是相同的单词，那么这样不同的单词最多只有26*26=676个了。

把单词连成一条长串，实际上是有向图的欧拉道路的打印结果。那么根据有向图里面欧拉道路的结论，除了起点和终点以外，其它的点的入度等于出度，起点的入度比出度少1，终点的出度比入度少1。对于这道题来说，我们只需要统计以某个字母为开头和结尾单词的个数，比方说，我们统计以m结尾的单词的个数（记为end）以及以m开头的单词的个数（记为front），对于a~z都要统计。我们仅仅允许出现1次end>front和1次front>end，其余情况end==front（所有的end都等于front也是可以的）。满足上述条件的就可以连成长串，否则不可以。当然，存在欧拉道路首先要连通，我们可以先搜索一次判断是否连通，这里的连通是指把相同的单词看成一个点，把有向图的方向忽略，当做无向图，判断是否连通。

#include<iostream>
#include<string>
#include<cstring>
#define MAXN 676
using namespace std;

int word[MAXN],vis[MAXN];//word数组保存不同的单词的数目，首字母*26+尾字母作为下标

void dfs(int cur)
{
	for(int i=0;i<MAXN;i++)
		if(word[i]&&!vis[i]&&(cur%26==i/26||cur/26==i%26))
		{
			vis[i]=1;
			dfs(i);
		}
}
int main()
{
	//freopen("in.txt","r",stdin);
	int i,N,T;
	string tmp;
	cin>>T;
	while(T--)
	{
		int first;
		cin>>N;
		memset(word,0,sizeof(word));
		for(i=0;i<N;i++)
		{
			int num,last;
			cin>>tmp;//输入单词
			last=tmp.length()-1;
			num=(tmp[0]-'a')*26+(tmp[last]-'a');//提取首尾字母，计算对应的下标
			word[num]++;
			if(i==0) first=num;//记下第一个单词，用于搜索
		}
		//先搜索，判断是否连通
		memset(vis,0,sizeof(vis));
		vis[first]=1;
		dfs(first);
		int ok=1;
		for(i=0;i<MAXN;i++)
			if(word[i]&&!vis[i])
			{ok=0;break;}
		if(ok==0)//如果不连通则一定不可以连成长串
		{
			cout<<"The door cannot be opened."<<endl;
			continue;
		}
		//再判断是否存在欧拉道路
		int front[26]={0},end[26]={0};
		for(i=0;i<MAXN;i++)
		{
			front[i/26]+=word[i];
			end[i%26]+=word[i];
		}
		int flag1=0,flag2=0;
		ok=1;
		for(i=0;i<26;i++)
		{
			if(front[i]==end[i]) continue;
			else if(front[i]-end[i]==1)
				flag1++;
			else if(end[i]-front[i]==1)
				flag2++;
			else {ok=0;break;}
			if(flag1>1||flag2>1) {ok=0;break;}
		}
		if(ok&&(flag1==0&&flag2==0||flag1==1&&flag2==1))
			cout<<"Ordering is possible."<<endl;
		else
			cout<<"The door cannot be opened."<<endl;
	}
	return 0;
}