首先用DFS判断是否连通，若连通，再逐个检查其顶点的入度和出度，以判断是否有一条有向欧拉路。
可是为什么会WA????

#include<stdio.h>
#include<string.h>

	long adj[26][26],indeg[26],outdeg[26];
   long visited[26];
   long flag,flagin,flagout;
   char mentioned[26];
   long first,last;
   long count;
   long ment,i,j,v,t;
   long n;
   char input[1010];
int main()
{
   long DFS(long);
   scanf("%d",&v);
   for(t=0;t<v;t++)
   {
	   scanf("%d",&n);
	   for(i=0;i<26;i++) {visited[i]=0; indeg[i]=0; outdeg[i]=0; }
	   for(i=0;i<26;i++) for(j=0;j<26;j++) adj[i][j]=0;
	   ment=0;flagin=0;flagout=0;
	   count=0;
	   for(i=0;i<n;i++)
	   {
		   scanf("%s",input);
		   first=input[0]-97;last=input[strlen(input)-1]-97;
		   for(j=0;j<ment;j++)
			   if((long)mentioned[j]-97==first) break;
		   if(j==ment) mentioned[ment++]=first+97;
		   for(j=0;j<ment;j++)
			   if((long)mentioned[j]-97==last) break;
		   if(j==ment) mentioned[ment++]=last+97;
		   adj[first][last]=1;
		   outdeg[first]++;indeg[last]++;
	   }
	   DFS((long)mentioned[0]-97);
	   if(count!=ment)
	   {
	      printf("The door cannot be opened.\n"); continue;
	   }
	   flag=1;
	   for (i=0;i<26;i++)
	   {
		   if(indeg[i]==outdeg[i]) continue;
		   if(indeg[i]>outdeg[i]+1 || outdeg[i]>indeg[i]+1) {flag=0;break;}
		   if(indeg[i]==outdeg[i]+1) {flagin++; continue;}
		   if(indeg[i]==outdeg[i]-1) {flagout++;continue;}
	   }
	  
	   if(flag==0 || flagin>1 || flagout>1 ||flagin!=flagout)
		   {
	      printf("The door cannot be opened.\n"); continue;
	   }
	   printf("Ordering is possible.\n");
   }
   return 0;
}
long DFS(long ch)
{
    
	count++;
	visited[ch]=1;
	for(i=0;i<26;i++)
	{
		if(adj[ch][i]>=1 && visited[i]==0) DFS(i);
	}
	for(i=0;i<26;i++)
	{
		if(adj[i][ch]>=1 && visited[i]==0) DFS(i);
	}
	return 0;
}

• Re:不知道为何会wa.... (1968) 1224730131 2013-01-24 14:11:20
• Re:不知道为何会wa.... (1968) 1224730131 2013-01-24 14:12:06