1 //Accepted    248 KB    125 ms  2 //欧拉回路  3 //以26个字母为定点，一个单词为从首字母到末尾字母的一条边  4 //下面就是有向图判断欧拉回路  5 //连通+节点入度和==出度和 或者 存在一对节点一个入度比出度大1，一个小1  6 #include <cstdio>  7 #include <cstring>  8 #include <iostream>  9 #include <queue> 10 using namespace std; 11 const int imax_n = 30; 12 int a[imax_n][imax_n]; 13 bool used[imax_n]; 14 bool vis[imax_n]; 15 int cnt_in[imax_n],cnt_out[imax_n]; 16 int n; 17 char s[1005]; 18 queue<int >q; 19 void bfs(int s) 20 { 21     while (!q.empty()) q.pop(); 22     //if (used[s]==0) return 0; 23     q.push(s); 24     vis[s]=1; 25     while (!q.empty()) 26     { 27         int x=q.front(); 28         q.pop(); 29         for (int i=1;i<imax_n;i++) 30         { 31             if (used[i]==1 && !vis[i] && a[x][i]) 32             { 33                 vis[i]=1; 34                 q.push(i); 35             } 36         } 37     } 38 } 39 bool judge() 40 { 41     int flag; 42     for (int i=1;i<=26;i++) 43     { 44         memset(vis,0,sizeof(vis)); 45         bfs(i); 46         flag=1; 47         for (int j=1;j<=26;j++) 48         if (used[j]==1 && !vis[j]) flag=0; 49         if (flag==1) return 1; 50     } 51     return 0; 52 } 53 bool slove() 54 { 55     int p,ne; 56     p=ne=0; 57     for (int i=1;i<=26;i++) 58     { 59         int t=cnt_in[i]-cnt_out[i]; 60         if (t==0) continue; 61         if (t==1) 62         { 63             p++; 64             if (p>=2) return 0; 65             continue; 66         } 67         if (t==-1) 68         { 69             ne++; 70             if (ne>=2) return 0; 71             continue; 72         } 73         return 0; 74     } 75     if (!(p==1 && ne==1 || p==0 && ne==0)) return 0; 76     return 1; 77 } 78 int main() 79 { 80     int T; 81     scanf("%d",&T); 82     while (T--) 83     { 84         scanf("%d",&n); 85         int x,y; 86         memset(a,0,sizeof(a)); 87         memset(used,0,sizeof(used)); 88         memset(cnt_in,0,sizeof(cnt_in)); 89         memset(cnt_out,0,sizeof(cnt_out)); 90         for (int i=0;i<n;i++) 91         { 92             scanf("%s",s); 93             int l=strlen(s); 94             x=s[0]-‘a‘+1; 95             y=s[l-1]-‘a‘+1; 96             used[s[0]-‘a‘+1]=true; 97             used[s[l-1]-‘a‘+1]=true; 98             a[x][y]=1; 99             cnt_out[x]++;100             cnt_in[y]++;101         }102         if (judge()==1 && slove()==1)103         printf("Ordering is possible.\n");104         else105         printf("The door cannot be opened.\n");106     }107     return 0;108 }