欧拉回路的一道不错的题目。（顺便总结下欧拉回路）
欧拉道路：能从无向图中的一个结点出发走出一条道路，每条边恰好经过一次。
如果一个无向图是连通的，且最多只有两个奇点（点的度数为奇数的点），则一定存在欧拉道路。
如果有两个奇点，则必须从其中一个奇点出发，另一个奇点终止；
如果奇点不存在，则可以从任意点出发，最终一定会回到该点。（称为欧拉回路）。
奇点不可能为奇数，一条边提供两个度，起点，终点，（假设有方向）则，度数必然两个两个增加，若奇点为奇数，则总的度数和必然为奇数。与度数两个两个增加矛盾。
如果为有向图：最多只能有两个点的入度不等于出度，而且其中一个必然是入度比出度大一（作为终点），另一个则为出度比入度大一（作为起点），若没有，则任意点为起点均可以，且最后必然会回到这点。
还有一个前提：不考虑边的方向的情况下，该图必须是连通的。
额，再说下题意。
给你很多个石板，然后按一定顺序排列，使这个字符串的最后一个字母和下一个字符串的首字母相同。
1e5的数据量，如果直接搜索会超时，（没试过，因为要把每个结点都试一遍，之后还要扫之后的每个），不知道会爆栈不……。
如果我们把每个字符串首字母当成起点，末字母当成终点，然后连线，想象出一个图（有向图），只需判断是否能构成一个欧拉道路即可。
先判断是否满足欧拉回路条件，然后用dfs判断该图是否连通。只需要判断有多少个结点在图上即可。
如果先判断是否连通的话，费时间比较长。
#include<cstdio>
#include<cstring>
const int MAXN=30;
const int inf=1000+10;
char temp[inf]; //输入的字符串
int G[MAXN][MAXN]; //判断有向图的边数，有一条+1；
int Gzero[MAXN],Gfinal[MAXN]; //起点的个数，终点的个数。即点的度数
bool letter[MAXN];
int nletter,cnt; //记录出现的字母个数，和最后判断多少个点在图上
bool start,end; //记录起点和终点是否只有一个
void dfs(int u){
if(cnt==nletter) return ;
if(!letter[u]) {letter[u]=true;cnt++;} //判断字母是否出现过
for(int i=0;i<26;i++) if(G[u][i]){G[u][i]=0;dfs(i);}
}
int main(){
//freopen("in.txt","r",stdin);
int T,n;
scanf("%d",&T);
while(T--){
int u=0,failed=0,x,y;
memset(G,0,sizeof(G));
memset(Gzero,0,sizeof(Gzero));
memset(Gfinal,0,sizeof(Gfinal));
memset(letter,0,sizeof(letter));
start=false; end=false; nletter=0,cnt=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s",temp);
int lt=strlen(temp)-1;
x=temp[0]-‘a‘; //将首尾字母当成数字存起来，a到z表达成0到25；
y=temp[lt]-‘a‘;
if(!letter[x]){nletter++;letter[x]=true;} //记录出现的字母的个数
if(!letter[y]){nletter++;letter[y]=true;}
Gzero[x]++; Gfinal[y]++; //每条边的起点和终点的度数
G[x][y]++; //记录有向边有多少条。不过好像记录过度数，标记下也行
}
for(int i=0;i<26;i++){
if(Gzero[i]==Gfinal[i]); //如果相等，则出度等于入度
else if(Gzero[i]==Gfinal[i]+1){ //如果出度比入度大一，只能为起点
if(!start){start=true;u=i;} //判断起点是否只出现过一次，并记录起点
else failed=1; //若出现不止一次，不存在欧拉回路
}
else if(Gzero[i]==Gfinal[i]-1){
if(!end) end=true; //与起点同理，不过不用记录终点
else failed=1;
}
else failed=1;
}
memset(letter,false,sizeof(letter)); //将字母全标记为假，dfs判断出现多少个字母
if(start && !failed) dfs(u); //如果存在欧拉回路且有唯一起点，递归判断
else if(!failed) dfs(x); //如果存在欧拉回路且没起点，随便dfs判断图是否连通
if(cnt!=nletter) failed=1; //如果有点不在图上，则不构成通路
if(failed) printf("The door cannot be opened.\n");
else printf("Ordering is possible.\n");
}
return 0;
}
uva 10129 - Play on Words,布布扣,bubuko.com
原文：http://blog.csdn.net/u013791747/article/details/20479513