#include<iostream>
using namespace std;

int degree[26],N,n;
string s;
bool adj[26][26],visited[26];

void Input()
{
 int i,j,t1,t2;
 char ch,cht;
 for(i=0;i<26;i++)
 {
  visited[i]=false;
  degree[i]=0;
  for(j=0;j<26;j++)
	  adj[i][j]=false;
 }

 scanf("%d",&n);
 getchar();
 for(i=0;i<n;i++)
 {
  ch=getchar();
  t1=ch-'a';
  while(1)
  {
  cht=getchar();
  if(cht>='a'&&cht<='z')ch=cht;
  else if(cht=='\n')break;
  }
  t2=ch-'a';
  adj[t1][t2]=true;
  visited[t1]=true;
  visited[t2]=true;
  ++degree[t1];//入度
  --degree[t2];//出度
 }
}

bool Deal()//根据欧拉回路的定义算出入度
{
 int i,f1,f2;
 f1=f2=0;
 for(i=0;i<26;i++)
	 if(degree[i]==1)f1++;
     else if(degree[i]==-1)f2++;
	 else if(degree[i]!=0){return false;}
 if((f1==1&&f2==1)||(f1==0&&f2==0))return true;
 else return false;
}

void DFS(const int &v)
{
 int i;
 visited[v]=false;
 for(i=0;i<26;i++)
	 if(adj[v][i]==true&&visited[i]==true)DFS(i);
}
int main()
{
 int i;
 cin>>N;
 while(N--)
 {
  Input();
  if(!Deal())cout<<"The door cannot be opened."<<endl;
  else {
  for(i=0;i<26;i++)
    if(visited[i]==true)break;
  DFS(i);//访问到的都变成了false
  for(i=0;i<26;i++)//再有true的点说明没有连通
	 if(visited[i]==true)break;
   if(i==26)cout<<"Ordering is possible."<<endl;
   else cout<<"The door cannot be opened."<<endl;
  }
 }
 return 0;
}

• Re:找着别人AC的代码对比了一下 没发现思想有错 可就是WA 大虾帮忙啊。。。。 (1517) wlp 2008-09-19 10:01:53