HDU/HDOJ 1116 Play on Words(并查集+欧拉通路)

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1116

离散数学的知识,囧,这一块没怎么学,基础很薄弱啊。

不过对于欧拉回路/通路的结论,倒是不难推出。

欧拉通路:除首尾结点外,其余结点入度等于出度,起点出度减入度等于1,终点入度减出度等于1

欧拉回路:所有结点的入度都等于出度

思路:将每一个单词的首尾字母当做结点,首尾字母间连线,判断最后形成的有向图能否形成欧拉通路/回路,用并查集。

这题直接参考了网上的。

代码:

[code lang=”cpp”]
#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;
}

[/code]

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注