http://acm.pku.edu.cn/JudgeOnline/problem?id=1386
这个题题意是给你一组单词，要判断是否能够构成一个
首尾相接的单词链，例如给出如下单词:
3
acm
malform
mouse
就可以构成 acm->malform->mous的单词链。
这种题实际上就是判断有向图的欧拉路的存在性。
也就是对所给的所有单词，所有出现过的不同的字母就是图上
的顶点，读入每一个单词，单词的首字母对应的点出度加1，末
字母对应的点入度加1，最后再来做判断。
最后构成的链一定是这样的:
对于上例就是：a->m->m->m->e;也就是所有字母对应的入度等于出度
或是除了端点的字母各自的出入度相差一以外其余的出度入度都相等，
就满足条件，能构成链。
那么对于所有出现过的字母，只用判断只有一个的出度为入度加1而
且只有一个的入度等于出度加1(如上例)，或所有点的出度等于入度
就可以了。当然首先图必须是连通的，这点很关键，这个可以用并查
集来做。这样这题其实就很简单了。
poj还有个2337也是类似的题，不过那个题还需要把最后的欧拉路找
出来。http://acm.pku.edu.cn/JudgeOnline/problem?id=2337
code：
Source Code
| Problem: 1386 |
|
User: lovecanon |
| Memory: 208K |
|
Time: 313MS |
| Language: C++ |
|
Result: Accepted |
#include<stdio.h>
#include<string.h>
struct node{
int in,out;
}degree[26];
int father[26],rank[26],mem[27],vis[26],top;
int find(int t){
int tmp=t;
while(father[tmp]!=tmp) tmp=father[tmp];
father[t]=tmp;
return tmp;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int i,n;
char buf[1001];
scanf("%d",&n);
for(i=0;i<26;i++) {father[i]=i;rank[i]=0;}
memset(degree,0,sizeof(degree));
memset(vis,0,sizeof(vis));
top=0;
for(i=0;i<n;i++){
scanf("%s",buf);
int a=buf[0]-'a',b=buf[strlen(buf)-1]-'a';
if(!vis[a]) {vis[a]=1;mem[++top]=a;}
if(!vis[b]) {vis[b]=1;mem[++top]=b;}
degree[a].out++;degree[b].in++;
a=find(a);b=find(b);
if(a!=b){
if(rank[a]<rank[b]) father[a]=b;
else{
father[b]=a;
if(rank[a]==rank[b]) rank[a]++;
}
}
}
int tmp=find(mem[1]),flag=0;
for(i=2;i<=top;i++) if(find(mem[i])!=tmp) {flag=1;break;}
if(flag) {printf("The door cannot be opened.\n");continue;}
int sum=0,flag1=0,flag2=0,ok=1;
for(i=1;i<=top && sum<=2 && ok;i++){
if(degree[mem[i]].in!=degree[mem[i]].out){
sum++;
if(degree[mem[i]].in==degree[mem[i]].out+1) flag1++;
else if(degree[mem[i]].out==degree[mem[i]].in+1) flag2++;
else ok=0;
}
}
if(ok){
if(flag1==1&&flag2==1 || flag1==0&&flag2==0) printf("Ordering is possible.\n");
else printf("The door cannot be opened.\n");
}
else printf("The door cannot be opened.\n");
}
//system("pause");
return 0;
}