这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。
题目传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1116
离散数学的知识，囧，这一块没怎么学，基础很薄弱啊。
不过对于欧拉回路/通路的结论，倒是不难推出。
欧拉通路：除首尾结点外，其余结点入度等于出度，起点出度减入度等于1，终点入度减出度等于1
欧拉回路：所有结点的入度都等于出度
思路：将每一个单词的首尾字母当做结点，首尾字母间连线，判断最后形成的有向图能否形成欧拉通路/回路，用并查集。
这题直接参考了网上的。
代码：
#include<stdio.h>
#include<string.h>
#define N 27
int out[N],in[N],flag[N],p[N],father[N];
int find(int x)
{
int r=x;
while(father[r]!=r)
r=father[r];
return r;
}
void Union(int a,int b)
{
int fx,fy;
fx=find(a);
fy=find(b);
if(fx!=fy)
father[fx]=fy;
}
int main()
{
int i,k,cnt,a,b,ncase,n;
char s[1002];
scanf("%d",&ncase);
while(ncase--)
{
for(i=0;i<26;i++)
father[i]=i; //初始化
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
memset(flag,0,sizeof(flag));
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%s",s);
a=s[0]-'a';
b=s[strlen(s)-1]-'a';
Union(a,b);
in[b]++;
out[a]++;
flag[a]=flag[b]=1;
}
cnt=0;
for(i=0;i<26;i++)
{
father[i]=find(i);
if(flag[i] && father[i]==i)
cnt++; //计算连通分支个数
}
if(cnt>1) //不是连通图
{
printf("The door cannot be opened.\n");
continue;
}
k=0;
for(i=0;i<26;i++)
{
if(flag[i] && in[i]!=out[i])
p[k++]=i; //计算入度不等于出度的结点数
}
if(k==0) //是欧拉回路
{
printf("Ordering is possible.\n");
continue;
}
if(k==2 && (out[p[0]]-in[p[0]]==1 && in[p[1]]-out[p[1]]==1
|| out[p[1]]-in[p[1]]==1 && in[p[0]]-out[p[0]]==1) )
{ //是欧拉通路
printf("Ordering is possible.\n");
continue;
}
printf("The door cannot be opened.\n");
}
return 0;
}