hdu-1116（欧拉回路+并查集）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1116

思路：将字符串的头元素和尾元素视为图的x，y节点，然后合并x，y。

如果这个图不连通，则门不能打开，如果路径是欧拉回路或者欧拉通路，则门可以打开。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[],b[],vis[],in[],out[];
char str[];
int f(int x)
{
if(x==a[x]) return a[x];
else
{
a[x]=f(a[x]);
return a[x];
}
}
void Merge(int x,int y)
{
int t1=f(x),t2=f(y);
if(t1!=t2)
{
a[t2]=t1;
}
}
int main(void)
{
int num,i,j,x,y,t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=;i<;i++)
{
a[i]=i;vis[i]=;
b[i]=;in[i]=;out[i]=;
}
for(j=;j<n;j++)
{
scanf("%s",str);
x=str[]-'a';
y=str[strlen(str)-]-'a';
Merge(x,y);
in[y]++;out[x]++;
vis[x]=;vis[y]=;
}
for(i=;i<;i++) a[i]=f(i);
num=;
for(i=;i<;i++)
if(vis[i]&&a[i]==i) num++;
if(num>)
{
printf("The door cannot be opened.\n");
}
else
{
num=;
for(i=;i<;i++)
if(vis[i]&&in[i]!=out[i]) b[num++]=i;
if(num==)
{
printf("Ordering is possible.\n");
}
else if(num==&&(out[b[]]-in[b[]]==&&in[b[]]-out[b[]]==||
out[b[]]-in[b[]]==&&in[b[]]-out[b[]]==))
printf("Ordering is possible.\n");
else printf("The door cannot be opened.\n");
}
}
return ;
}