http://poj.org/problem?id=1386
题意：给定若干个单词，若前一个的尾字母和后一个单词的首字母相同，则这两个单词可以连接，问是否所有的单词都能连接起来。
思路：欧拉路的判断，且为有向图，将每个单词的首尾字母看做节点，中间字母看做边，建图。
(1)用并查集判断图是否连通。
(2)判断奇数节点的个数为0或2个，其余节点均入度=出度。
#include <stdio.h>
#include <string.h>
const int N=;
const int M=;
int in[M];
int out[M];
int f[M],vis[M];
void init()
{
for (int i = ; i < M; i ++)
{
in[i] = ;
out[i] = ;
f[i] = i;
vis[i] = ;
}
}
int find(int x)
{
if (x!=f[x])
f[x] = find(f[x]);
return f[x];
}
void merge(int x,int y)
{
f[find(x)] = find(y);
}
int main()
{
int n,m;
scanf("%d",&n);
while(n--)
{
char str[N];
int v,u,len;
scanf("%d",&m);
init();
for (int i = ; i <= m; i ++)
{
scanf("%s",str);
len = strlen(str);
u = str[]-'a';
v = str[len-]-'a';
vis[u] = ;
vis[v] = ;
in[v]++;
out[u]++;
merge(u,v);
}
int flag = ;
int cnt1 = ,cnt2 = ;
int father = find(v);
for (int i = ; i < M; i ++)//判断图是否连通
{
if (vis[i]&&find(i)!=father)
{
printf("The door cannot be opened.\n");
flag = ;
break;
}
}
if(flag)//判断度数
{
for (int i = ; i < M; i ++)
{
if(vis[i]&&in[i]-out[i]==)
cnt1++;//入度比出度大一的节点的个数
else if (vis[i]&&out[i]-in[i]==)
cnt2++;//出度比入度大一的节点的个数
else if (vis[i]&&in[i]!=out[i])
{
flag = ;
break;
}
}
if ((cnt1==&&cnt2==||cnt1+cnt2==)&&flag)
printf("Ordering is possible.\n");
else
printf("The door cannot be opened.\n");
} }
return ; }