1 /* 2   题意：单词拼接，前一个单词的末尾字母和后一个单词的开头字母相同 3   思路：将一个单词的开头和末尾单词分别做两个点并建一条有向边！然后判断是否存在欧拉回路或者欧拉路  4  5   再次强调有向图欧拉路或欧拉回路的判定方法： 6 (1)有向图G为欧拉图(存在欧拉回路)，当且仅当G的基图连通，且所有顶点的入度等于出度。 7 (2)有向图G为半欧拉图(存在欧拉道路)，当且仅当G的基图连通，且存在顶点u的入度比出度大1、v的入度比出度小1， 8    其它所有顶点的入度等于出度（顶点u，v的个数必须都是1）。 9    10    求该图的连通性的时候，只要求该有向图是弱连通的就可以了！所以转换为无向图的连通问题！ 11 */ 12 #include<iostream>13 #include<cstring>14 #include<cstdio>15 #include<algorithm>16 using namespace std;17 18 int g[30][30];19 char ch[1005];20 int vis[30], used[30];21 int inD[30], outD[30];22 23 void dfs(int u){24    vis[u]=1;25    for(int i=0; i<26; ++i)26       if(g[u][i] && !vis[i])27          dfs(i);28 } 29 30 bool checkDeg(){31     int inOut=0, outIn=0;32     for(int i=0; i<26; ++i)33        if(used[i] && inD[i]-outD[i]!=0){34           if(inD[i]-outD[i]>1 || inD[i]-outD[i]<-1) return false;35           else inD[i]-outD[i]>0 ? ++inOut : ++outIn; 36        }37     return (inOut==1 && outIn==1) || (inOut==0 && outIn==0);38 }39 40 int main(){41     int n, t;42     scanf("%d", &t);43     while(t--){44         scanf("%d", &n);45         memset(vis, 0, sizeof(vis));46         memset(used, 0, sizeof(used));47         memset(g, 0, sizeof(g));48         memset(inD, 0, sizeof(inD));49         memset(outD, 0, sizeof(outD)); 50         while(n--){51            scanf("%s", ch);52            int u=ch[0]-‘a‘, v=ch[strlen(ch)-1]-‘a‘;53            g[u][v]=g[v][u]=1;//无向图的连通性 即是有向图的弱连通 54            used[u]=used[v]=1;55            ++inD[v];56            ++outD[u];57         }58         bool flag=true;59         for(int i=0; i<26; ++i)60            if(used[i]){61               dfs(i);62               break;63            }64         for(int i=0; i<26; ++i)65            if(used[i] && !vis[i]){66               flag=false;67               break;68            }69         if(flag && !checkDeg())70            flag=false;71         if(flag)72            printf("Ordering is possible.\n"); 73         else printf("The door cannot be opened.\n");74     }75     return 0;76 }