题目描述：
有n个单词n<100000，单词长度不超过1000，全由小写字母组成。当一个单词的首字母是另一个单词的末尾字母时，可以连接在一起。 要求这些单词能否全部连接在一起。可能出现重复的单词，须多次使用。
分析：
问题简化之后就变成了一个一笔画问题，也就是求一个图是否是存在欧拉通路。只不过这里的图是有向图。
离散数学书里可以找到关于“无向图”欧拉通路的广为人知结论：
无向连通图存在欧拉通路，当且仅当度为奇数的顶点不超过2个。顶点的“度”等于与它相连的边的条数。
特殊地，无向连通图存在欧拉回路，当且仅当所有顶点的度为偶数。
对于此题也不难推得以下结论：
有向连通图存在欧拉通路，当且仅当不超过2个顶点的入度不等于出度，且入度与出度的差不大于1。
可以这样理解：若存在欧拉通路，必然从起点出发，途径若其他所有顶点，最后停留在终点。对于路途中的顶点，必然进去一次就需要出来一次，所以入度必定等于出度；而对于起点和终点，起点的出度比入度大1，终点的入度比出度大1。若有向图是欧拉回路，则所有顶点的入度等于出度。即从任意顶点出发都可以遍历整个图。
写程序的时候不要忘了判断图是否连通。
这里由个优化，可以使用并查集来判断图的连通性，判断时把图当作是无向图来判断。即只需要有向图弱连通即可。
贴一下代码，挺快的~：
#include <stdio.h>
#include <string.h>
#define N 1005
#define clr(a) memset(a,0,sizeof(a))
#define abs(x) ((x)>0?(x):-(x))
int a[30],b[30];
char s[N];
char f[30];
char root(char p){
int t,q=p;
while(f[q]) q=f[q];
while(f[p]){
t=f[p];
f[p]=q;
p=t;
}
return q;
}
int main()
{
int i,j,k,m,n,T;
int count,flag,con;
int p,q,r,v='a'-1;
scanf("%d",&T);
while(T--)
{
//init
clr(a); clr(b);
clr(f);
//input
scanf("%d",&n);
getchar();
for(i=0;i<n;i++){
gets(s);
m=strlen(s)-1;
a[s[0]-v]++;
b[s[m]-v]++;
p=root(s[0]-v);
q=root(s[m]-v);
if(p!=q) f[p]=q;
}
//connected
con=1;
j=1;
while(!(a[j]+b[j])) j++;
r=root(j);
for(i=j;i<=26&&con;i++)
if((a[i]+b[i])&&root(i)!=r)
con=0;
//judge
count=0;
flag=con;
for(i=1;i<=26&&flag;i++){
if(a[i]!=b[i]) count++;
if(count>2||abs(a[i]-b[i])>1) flag=0;
}
//output
if(flag&&count<=2) puts("Ordering is possible.");
else puts("The door cannot be opened.");
}
//system("pause");
return 0;
}