本文主要是介绍hdu（（1116））欧拉回路和通路。。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：给你n个单词，要你判断这些单词能不能首尾相连。
把每个单词的首尾字母有一条有向边相连，记录每个字母的入度和出度把每两个能连的单词用一条有向边边相连，既是要判断该有向图图是否有欧拉通路，
至于欧拉回路和欧拉通路的判定可以总结为如下：
1）所有的点联通
2）欧拉回路中所有点的入度和出度一样。
3）欧拉通路中终点的入度 - 出度 = 1，起点的 初度 - 入度 = 1， 其他的所有点入度 = 出度；
#include<stdio.h>
#include<string.h>
#include<math.h>
int pre[50];
int in[50],out[50];
int find(int k)
{
if(pre[k]==k)
return k;
pre[k]=find(pre[k]);
return pre[k];
}
int main()
{
int n,i,len,t,a,b,f1,f2,s,s1,s2;
char str[1005];
scanf("%d",&t);
while(t--)
{
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
for(i=0;i<26;i++)
pre[i]=i;
scanf("%d",&n);
while(n--)
{
scanf("%s",str);
len=strlen(str);
a=str[0]-'a';
b=str[len-1]-'a';
in[a]++;
out[b]++;
f1=find(a);
f2=find(b);
if(f1!=f2)
pre[f1]=f2;
}
s=0;
for(i=0;i<26;i++)
if(pre[i]==i&&(in[i]+out[i]))
s++;
if(s>1)
{
printf("The door cannot be opened.\n");
continue;
}
s1=0;s2=0;
for(i=0;i<26;i++)
{
if(in[i]!=out[i])
{
s1++;
if(abs(in[i]-out[i])==1)
s2++;
}
}
if(s1==0)
{
printf("Ordering is possible.\n");
continue;
}
if(s1==2&&s2==2)
{
printf("Ordering is possible.\n");
continue;
}
printf("The door cannot be opened.\n");
}
return 0;
}
这篇关于hdu（（1116））欧拉回路和通路。。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
