学步园

              题意:

                        有一串单词...若有一个单词的最后一个字符等于另一个单词的第一个字符.. 则他们可以接起来..问这些单词能否接成一串...

              题解:

                        这题目的意思求是否存在哈密顿通路(每个单词是一个点..找一条路径恰好经过每个单词一次)...但这么多点..还是个NP难..直接做不切实际...

                        因为问题的特殊性..可以进行转化...不以单词为点了..而以单词为边..字母为点...一个单词就转化成了其第一个字母指向最后一个字母的有向边...那么题目就转化成了求该有向图是否存在欧拉通(回)路(单词为边..那么就变成了要从一个字母出发便利所有的边的路径)..

                        判断有向图是否是欧拉通路:

                         1、一个有向图存在欧拉回路必定也存在欧拉通路...因为通路的定义包括了回路

                         2、不考虑为欧拉回路的情况..一个有向图是欧拉通路就必须有一个点出度-入度=1,一个点入度-出度=1..这两点就是欧拉通路的起点和终点..并且该图连通

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<time.h>
#include<map>
#include<algorithm>
#define ll long long
#define eps 1e-5
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 100005
#define MAXM 500005
using namespace std;  
int P[2][26],father[26];
bool used[26];
char s[1005];
int getfather(int x)
{
       if (father[x]==x) return x;
       return father[x]=getfather(father[x]);
}
int main()
{        
       int i,cases,n,m,x,y,t1,t2; 
       scanf("%d",&cases);
       while (cases--)
       {
               scanf("%d",&n); 
               memset(used,false,sizeof(used));
               memset(P,0,sizeof(P));
               for (i=0;i<26;i++) father[i]=i;
               for (i=1;i<=n;i++)
               {
                      scanf("%s",s+1);
                      x=s[1]-'a',y=s[strlen(s+1)]-'a'; 
                      P[0][x]++,P[1][y]++;
                      father[getfather(x)]=getfather(y);
                      used[x]=used[y]=true;
                      m=getfather(x);
               } 
               if (n==1) 
               {
                      printf("Ordering is possible.\n");
                      continue;
               } 
               for (i=0;i<26;i++)
                  if (used[i] && getfather(i)!=m) break;
               if (i<26)
               {
                      printf("The door cannot be opened.\n");
                      continue;
               }
               t1=t2=0;
               for (i=0;i<26;i++)
               {
                      if (P[0][i]==P[1][i]) continue;
                      if (P[0][i]+1==P[1][i]) t1++;
                      else
                      if (P[1][i]+1==P[0][i]) t2++;
                      else break;
               }
               if (i<26 || !(t1==1 && t2==1 || !t1 && !t2))
                      printf("The door cannot be opened.\n"); 
                 else 
                      printf("Ordering is possible.\n");
       }
       return 0;
}