zoj 2016 poj 1386 Play on Words Errage+DFS
5657 ワード
私の新しいブログ:http://xiang578.top/
#include<stdio.h>
#include<string.h>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int mp[50][50],in[50],out[50],vis[50],use[50];
string str;
void dfs(int u)
{
//printf("%d
",u);
vis[u]=1;
for(int v=0;v<26;v++)
{
if(mp[u][v]&&!vis[v])
{
dfs(v);
}
}
}
int main()
{
int _,i,n,u,v;
int f1,f2,st,ed,f;
scanf("%d",&_);
while(_--)
{
scanf("%d",&n);
memset(mp,0,sizeof(mp));
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
memset(vis,0,sizeof(vis));
memset(use,0,sizeof(use));
for(i=0;i<n;i++)
{
cin>>str;
u=str[0]-'a';
v=str[str.size()-1]-'a';
out[u]++;
in[v]++;
mp[u][v]++;
use[u]=1;
use[v]=1;
}
f1=f2=0;
st=-1;
for(i=0;i<26;i++)
{
if(!use[i]) continue;
if(in[i]==out[i])
{
if(st==-1) st=i;
}
else if(in[i]-out[i]==1)
{
f1++;
if(f1>=2) break;
}
else if(out[i]-in[i]==1)
{
st=i;
f2++;
if(f2>=2) break;
}
else
{
f1=f2=-1;
break;
}
}
if((f1==0&&f2==0)||(f1==1&&f2==1))
{
dfs(st);
for(i=0,f=1;i<26;i++)
{
if(!vis[i]&&use[i])
{
f=0;break;
}
}
}
else f=0;
if(f) printf("Ordering is possible.
");
else printf("The door cannot be opened.
");
}
return 0;
}
私の新しいブログ:http://xiang578.top/