UVa-10129 Play on Words

  1 #include <bits/stdc++.h>
  2 
  3 const int maxn = 28;
  4 using namespace std;
  5 
  6 int G[maxn][maxn];
  7 int tmpG[maxn][maxn];
  8 int known[maxn];
  9 void DFS(int s)
 10 {
 11     for(int u=0; u<maxn; u++)
 12     {
 13         if(!known[u]&&tmpG[s][u])
 14         {
 15             known[u] = 1;
 16             DFS(u);
 17         }
 18     }
 19     return ;
 20 }
 21 
 22 bool bing(int vnum)
 23 {
 24     int count = 0;
 25     DFS(0);
 26     for(int i = 0;i < maxn;i ++)
 27     {
 28         if(known[i]>0)
 29             count ++;
 30     }
 31     return count==vnum;
 32 }
 33 
 34 int main()
 35 {
 36     int T;
 37     cin >> T;
 38     while(T --)
 39     {
 40         memset(G,0,sizeof(G));
 41         memset(tmpG,0,sizeof(tmpG));
 42         memset(known,0,sizeof(known));
 43         int vnum = 0;
 44         int v[maxn] {0};
 45         int n;
 46         cin >> n;
 47 
 48         int out[maxn] {0};
 49         int in[maxn] {0};
 50 
 51         vector<int> diff;
 52         while(n --)
 53         {
 54             string tmp;
 55             cin >> tmp;
 56             G[tmp[0]-'a'][tmp[tmp.size()-1]-'a'] ++;
 57             tmpG[tmp[0]-'a'][tmp[tmp.size()-1]-'a'] = 1;
 58             tmpG[tmp[tmp.size()-1]-'a'][tmp[0]-'a'] = 1;
 59             if(v[tmp[0]-'a']==0)
 60             {
 61                 v[tmp[0]-'a'] = 1;
 62                 vnum ++;
 63             }
 64             if(v[tmp[tmp.size()-1]-'a']==0)
 65             {
 66                 v[tmp[tmp.size()-1]-'a'] = 1;
 67                 vnum ++;
 68             }
 69         }
 70 
 71         if(!bing(vnum))
 72         {
 73             cout << "The door cannot be opened." << endl;
 74             continue;
 75         }
 76 
 77         for(int i = 0; i < maxn; i ++)
 78         {
 79             int sum = 0;
 80             for(int j = 0; j < maxn; j ++)
 81             {
 82                 sum += G[i][j];
 83             }
 84             in[i] = sum;
 85         }
 86 
 87         for(int i = 0; i < maxn; i ++)
 88         {
 89             int sum = 0;
 90             for(int j = 0; j < maxn; j ++)
 91             {
 92                 sum += G[j][i];
 93             }
 94             out[i] = sum;
 95         }
 96 
 97         for(int i = 0; i < maxn; i ++)
 98         {
 99             if(in[i]!=out[i])
100                 diff.push_back(in[i]-out[i]);
101         }
102 
103         if(diff.size()==0)
104         {
105             cout << "Ordering is possible." << endl;
106             continue;
107         }
108         else if(diff.size()==2)
109         {
110             if(diff[0]==-1&&diff[1]==1||diff[0]==1&&diff[1]==-1)
111             {
112                 cout << "Ordering is possible." << endl;
113                 continue;
114             }
115         }
116         cout << "The door cannot be opened." << endl;
117     }
118     return 0;
119 }