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[][];

 char ch[];

 int vis[], used[];

 int inD[], outD[];

 void dfs(int u){

    vis[u]=;

    for(int i=; i<; ++i)

       if(g[u][i] && !vis[i])

          dfs(i);

 } 

 bool checkDeg(){

     int inOut=, outIn=;

     for(int i=; i<; ++i)

        if(used[i] && inD[i]-outD[i]!=){

           if(inD[i]-outD[i]> || inD[i]-outD[i]<-) return false;

           else inD[i]-outD[i]> ? ++inOut : ++outIn;

        }

     return (inOut== && outIn==) || (inOut== && outIn==);

 }

 int main(){

     int n, t;

     scanf("%d", &t);

     while(t--){

         scanf("%d", &n);

         memset(vis, , sizeof(vis));

         memset(used, , sizeof(used));

         memset(g, , sizeof(g));

         memset(inD, , sizeof(inD));

         memset(outD, , sizeof(outD));

         while(n--){

            scanf("%s", ch);

            int u=ch[]-'a', v=ch[strlen(ch)-]-'a';

            g[u][v]=g[v][u]=;//无向图的连通性 即是有向图的弱连通

            used[u]=used[v]=;

            ++inD[v];

            ++outD[u];

         }

         bool flag=true;

         for(int i=; i<; ++i)

            if(used[i]){

               dfs(i);

               break;

            }

         for(int i=; i<; ++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 ;

 }