| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
有限图判欧拉回路—coken#include <iostream>
#include <string.h>
#include <set>
using namespace std;
const int MAXN=30;
char buf[1005];
set<int> vec;
int n;
int par[MAXN],indeg[MAXN],outdeg[MAXN];
void prep()
{
for(int i=0;i<MAXN;i++)
{
par[i]=i;
}
}
int fnd(int x)
{
if(par[x]==x)
{
return x;
}
return par[x]=fnd(par[x]);
}
void unite(int x,int y)
{
int a=fnd(x);
int b=fnd(y);
par[b]=a;
}
int main()
{
int T;
cin>>T;
while(T--)
{
vec.clear();
prep();
memset(indeg,0,sizeof(indeg));
memset(outdeg,0,sizeof(outdeg));
cin>>n;
for(int i=0;i<n;i++)
{
cin>>buf;
int len=strlen(buf);
int u=buf[0]-'a';
int v=buf[len-1]-'a';
unite(u,v);
vec.insert(u);
vec.insert(v);
outdeg[u]++;
indeg[v]++;
}
int root=-1;
int s=0;
int c1=0,c2=0,c3=0;
for(set<int>:: iterator it=vec.begin();it!=vec.end();it++)
{
int rt=fnd(*it);
if(root!=rt)
{
root=rt;
s++;
}
if(outdeg[*it]-indeg[*it]==1)
{
c1++;
}
else if(outdeg[*it]==indeg[*it])
{
c2++;
}
else if(indeg[*it]-outdeg[*it]==1)
{
c3++;
}
else ;
}
if(s==1)
{
if((c1==1&&c3==1&&c2==vec.size()-2)||(c1==0&&c3==0&&c2==vec.size()))
{
cout<<"Ordering is possible."<<endl;
}
else cout<<"The door cannot be opened."<<endl;
}
else
{
cout<<"The door cannot be opened."<<endl;
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator