UVa10129 判断有向图中是否存在欧拉回路

 #include<iostream>

    
 #include<cstring>
    
 #include<cstdlib>
    
 #include<cstdio>
    
 #include<cmath>
    
 #include<string>
    
 #include<map>
    
 #include<set>
    
 #include<algorithm>
    
 #include<vector>
    
 #include<stack>
    
 #include<sstream>
    
 #define ll long long
    
 using namespace std;
    
 /**********************************************************/
    
 const int M_NUM_MAX = 100000+10;
    
 const int M_INT_MAX = 0x7fffffff;
    
 const double M_DBL_MAX = 1.7976931348623158e+308;
    
 const double M_DBL_MIN = 2.2250738585072014e-308;
    
 int theMap[30][30],inAndOut[30][2];
    
 int vis[30],exist[30];
    
 int n,num;
    
 /**********************************************************/
    
 int min_2 (int x,int y) {return x<y?x:y;}
    
 int max_2 (int x,int y) {return x>y?x:y;}
    
 void dfs (int i)
    
 {
    
   vis[i]=1;//每遍历一个点都做标记
    
   num++;
    
   for (int j=0;j<30;j++)
    
     if ((theMap[i][j]>0||theMap[j][i]>0)&&!vis[j])//底图，去掉箭头
    
       dfs (j); 
    
 }
    
 /**********************************************************/
    
 int main()
    
 {
    
   //freopen ("in.txt","r",stdin);
    
   int t;
    
   scanf ("%d",&t);
    
   while (t--)
    
   {
    
     memset (vis,0,sizeof (vis));
    
     memset (theMap,0,sizeof (theMap));
    
     memset (inAndOut,0,sizeof (inAndOut));
    
     memset (exist,0,sizeof (exist));
    
     scanf ("%d",&n);
    
     char s[1010];
    
     for (int i=0;i<n;i++){
    
       scanf ("%s",s);
    
       theMap[s[0]-'a'][s[strlen(s)-1]-'a']++;
    
       exist[s[0]-'a']=exist[s[strlen(s)-1]-'a']=1;
    
     }
    
     int sum=0;
    
     for (int i=0;i<30;i++)//判断所有单词首尾中有几个字母，即图中点的个数
    
       if (exist[i])
    
         sum++;
    
     bool success=false;
    
     for (int i=0;i<30;i++){
    
       num=0;
    
       memset (vis,0,sizeof (vis));
    
       dfs(i);
    
       if (num==sum)//对图进行dfs，记录遍历点的个数，如果能遍历图中所有的点，说明底图是连通的
    
         break;
    
     }
    
     if (num==sum){
    
       int a[30];
    
       for (int i=0;i<30;i++)
    
         for (int j=0;j<30;j++){//求出所有点的入度和出度
    
           inAndOut[i][0]+=theMap[i][j];
    
           inAndOut[i][1]+=theMap[j][i];
    
         }
    
       int x=0;
    
       for (int i=0;i<30;i++)
    
         if (inAndOut[i][0]!=inAndOut[i][1])
    
           a[x++]=inAndOut[i][0]-inAndOut[i][1];
    
       //printf ("%d\n",x);
    
       if (x==0||(x==2&&a[0]*a[1]==-1) )//若所有点入度=出度，或者一个点入度=出度-1，出度=入度-1，说明存在欧拉回路
    
         success=true;
    
     }
    
     if (success)
    
       printf ("Ordering is possible.\n");
    
     else
    
       printf ("The door cannot be opened.\n");
    
   }
    
   return 0;
    
 }