hdu 1116 Play on Words

http://acm.hdu.edu.cn/showproblem.php?pid=1116

欧拉通路和欧拉回路

 #include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 1000
using namespace std; int f[maxn],in[maxn],ou[maxn],a[maxn];
bool vis[maxn];
int n;
char str[maxn]; int find(int x)
{
if(x==f[x]) return x;
return f[x]=find(f[x]);
} void union1(int x,int y)
{
int fx=find(x);
int fy=find(y);
if(fx!=fy)
f[fx]=fy;
} void inti()
{
for(int i=; i<; i++)
f[i]=i;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
inti();
memset(in,,sizeof(in));
memset(ou,,sizeof(ou));
memset(vis,false,sizeof(vis));
for(int i=; i<n; i++)
{
scanf("%s",str);
int k=strlen(str);
ou[str[]-'a']++;
in[str[k-]-'a']++;
vis[str[]-'a']=true;
vis[str[k-]-'a']=true;
union1(str[]-'a',str[k-]-'a');
}
int ans=;
for(int i=; i<; i++)
{
if(vis[i]&&f[i]==i)
ans++;
}
if(ans>)
{
printf("The door cannot be opened.\n");
continue;
}
int m1=,m2=;
bool flag=true;
for(int j=; j<; j++)
{
if(vis[j]&&in[j]!=ou[j])
{
if(in[j]-ou[j]==)
{
m1++;
}
else if(ou[j]-in[j]==)
{
m2++;
}
else flag=false;
}
}
if(flag&&((m1==&&m2==)||(m1==&&m2==)))
printf("Ordering is possible.\n");
else
printf("The door cannot be opened.\n");
}
return ;
}
上一篇:大海航行靠舵手 华为云靠什么征服K8S?


下一篇:cocos2dx学习,转摘一些链接