1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 using namespace std; 5 const int N=26; 6 int pre[N]; 7 int IN[N],OT[N],p[N]; 8 bool vis[N]; 9 char str[1005];10 void Init()11 {12     memset(vis,0,sizeof(vis));13     memset(IN,0,sizeof(IN));14     memset(OT,0,sizeof(OT));15     for(int i=0;i<N;i++)16         pre[i]=i;17 }18 int Find(int x)19 {20     if(pre[x]!=x)21         pre[x]=Find(pre[x]);22     return pre[x];23 }24 void Union(int x,int y)25 {26     x=Find(x);27     y=Find(y);28     if(x==y) return;29     pre[x]=y;30 }31 int main()32 {33     int T,n;34     scanf("%d",&T);35     while(T--)36     {37         Init();38         scanf("%d",&n);39         while(n--)40         {41             scanf("%s",str);42             int len=strlen(str);43             int x=str[0]-‘a‘;44             int y=str[len-1]-‘a‘;45             Union(x,y);46             OT[x]++;47             IN[y]++;        // 记录节点 a 和 b的入度和出度48             vis[x]=vis[y]=1;    //标记节点 a 和 b的出现49         }50         int cnt=0;51         for(int i=0;i<N;i++)52         {53             pre[i]=Find(i);     //找出每个节点的 BOSS54             if(vis[i]&&pre[i]==i)55                 cnt++;  // 统计最终 BOSS 即根节点的个数 。56         }57         if(cnt > 1)//图不连通58         {59             puts("The door cannot be opened.");60             continue;61         }62         int k=0;63         for(int i=0;i<N;i++)64         {65             if(vis[i]&&IN[i]!=OT[i])66                 p[k++]=i; //统计入度和出度不相等的点的信息67         }68         if(k==0)    //欧拉回路，即环69         {70             puts("Ordering is possible.");71             continue;72         }73         if(k==2&&((OT[p[0]]-IN[p[0]]==1&&IN[p[1]]-OT[p[1]]==1)||(OT[p[1]]-IN[p[1]]==1&&IN[p[0]]-OT[p[0]]==1))) //欧拉通路起点出度减入度等于1，终点入度减出度等于1。74         {75             puts("Ordering is possible.");76             continue;77         }78         puts("The door cannot be opened.");79     }80     return 0;81 }