poj 1386 Play on Words(有向图欧拉回路)

/*
  题意：单词拼接，前一个单词的末尾字母和后一个单词的开头字母相同
  思路：将一个单词的开头和末尾单词分别做两个点并建一条有向边！然后判断是否存在欧拉回路或者欧拉路 

  再次强调有向图欧拉路或欧拉回路的判定方法：
(1)有向图G为欧拉图(存在欧拉回路)，当且仅当G的基图连通，且所有顶点的入度等于出度。
(2)有向图G为半欧拉图(存在欧拉道路)，当且仅当G的基图连通，且存在顶点u的入度比出度大1、v的入度比出度小1，
   其它所有顶点的入度等于出度（顶点u，v的个数必须都是1）。

   求该图的连通性的时候，只要求该有向图是弱连通的就可以了！所以转换为无向图的连通问题！
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int g[30][30];
char ch[1005];
int vis[30], used[30];
int inD[30], outD[30];

void dfs(int u){
   vis[u]=1;
   for(int i=0; i<26; ++i)
      if(g[u][i] && !vis[i])
         dfs(i);
} 

bool checkDeg(){
    int inOut=0, outIn=0;
    for(int i=0; i<26; ++i)
       if(used[i] && inD[i]-outD[i]!=0){
          if(inD[i]-outD[i]>1 || inD[i]-outD[i]<-1) return false;
          else inD[i]-outD[i]>0 ? ++inOut : ++outIn;
       }
    return (inOut==1 && outIn==1) || (inOut==0 && outIn==0);
}

int main(){
    int n, t;
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        memset(vis, 0, sizeof(vis));
        memset(used, 0, sizeof(used));
        memset(g, 0, sizeof(g));
        memset(inD, 0, sizeof(inD));
        memset(outD, 0, sizeof(outD));
        while(n--){
           scanf("%s", ch);
           int u=ch[0]-'a', v=ch[strlen(ch)-1]-'a';
           g[u][v]=g[v][u]=1;//无向图的连通性 即是有向图的弱连通
           used[u]=used[v]=1;
           ++inD[v];
           ++outD[u];
        }
        bool flag=true;
        for(int i=0; i<26; ++i)
           if(used[i]){
              dfs(i);
              break;
           }
        for(int i=0; i<26; ++i)
           if(used[i] && !vis[i]){
              flag=false;
              break;
           }
        if(flag && !checkDeg())
           flag=false;
        if(flag)
           printf("Ordering is possible.\n");
        else printf("The door cannot be opened.\n");
    }
    return 0;
}