链接：http://vjudge.net/problem/viewProblem.action?id=19492
描述：单词接龙
思路：求欧拉回路或欧拉道路。
首先建图，以字母为节点，单词为边。因为单词不可能倒序，所以是有向图。
判断图的连通性，dfs就可以做到，把它当成无向图就好了。然后判断点的出入度就可以判断是不是欧拉回路或者欧拉道路。
下面是我的实现。
1 #include2 #include 3 #include 4 using namespace std; 5 #define Max 30 6 #define MaxLen 1010 7 int T,n,Bgn; 8 int Edge[Max][Max],Chu[Max],Ru[Max]; 9 bool vis[Max];10 char str[MaxLen];11 inline void Get_int(int &Ret)12 {13 char ch;14 bool flag=false;15 for(;ch=getchar(),ch<'0'||ch>'9';)16 if(ch=='-')17 flag=true;18 for(Ret=ch-'0';ch=getchar(),ch>='0'&&ch<='9';Ret=Ret*10+ch-'0');19 flag&&(Ret=-Ret);20 }21 inline void Read()22 {23 Get_int(n);24 memset(vis,false,sizeof(vis));25 memset(Chu,0,sizeof(Chu));26 memset(Ru,0,sizeof(Ru));27 memset(Edge,0,sizeof(Edge));28 int i,u,v,Len;29 for(i=1;i<=n;i++)30 {31 do32 {33 scanf("%s",str);34 Len=strlen(str);35 }while(!Len);36 u=str[0]-'a'+1; v=str[Len-1]-'a'+1;37 //if(u==v) continue;38 Edge[u][v]++;Edge[v][u]++;39 Chu[u]++;Ru[v]++;40 vis[u]=vis[v]=true;41 }42 Bgn=u;43 }44 void Dfs(int u)45 {46 vis[u]=false;47 for(int i=1;i<=26;i++)48 if(Edge[u][i]&&vis[i])49 Dfs(i);50 }51 inline bool Solve()52 {53 int i,ch=0,ru=0;54 Dfs(Bgn);55 for(i=1;i<=26;i++)56 {57 if(vis[i])58 return false;59 if(Chu[i]!=Ru[i])60 {61 if(Chu[i]-Ru[i]==1)62 ch++;63 else if(Ru[i]-Chu[i]==1)64 ru++;65 else66 return false;67 }68 }69 if((ch==1&&ru==1)||(ch==0&&ru==0))70 return true;71 return false;72 }73 int main()74 {75 Get_int(T);76 while(T--)77 {78 Read();79 if(Solve())80 printf("Ordering is possible.\n");81 else82 printf("The door cannot be opened.\n");83 }84 return 0;85 }