hdu 1116 Play on Words

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define maxn 1000
 5 using namespace std;
 6 
 7 int f[maxn],in[maxn],ou[maxn],a[maxn];
 8 bool vis[maxn];
 9 int n;
10 char str[maxn];
11 
12 int find(int x)
13 {
14     if(x==f[x]) return x;
15     return f[x]=find(f[x]);
16 }
17 
18 void union1(int x,int y)
19 {
20     int fx=find(x);
21     int fy=find(y);
22     if(fx!=fy)
23     f[fx]=fy;
24 }
25 
26 void inti()
27 {
28     for(int i=0; i<26; i++)
29     f[i]=i;
30 }
31 
32 int main()
33 {
34     int t;
35     scanf("%d",&t);
36     while(t--)
37     {
38         scanf("%d",&n);
39         inti();
40         memset(in,0,sizeof(in));
41         memset(ou,0,sizeof(ou));
42         memset(vis,false,sizeof(vis));
43         for(int i=0; i<n; i++)
44         {
45             scanf("%s",str);
46             int k=strlen(str);
47             ou[str[0]-‘a‘]++;
48             in[str[k-1]-‘a‘]++;
49             vis[str[0]-‘a‘]=true;
50             vis[str[k-1]-‘a‘]=true;
51             union1(str[0]-‘a‘,str[k-1]-‘a‘);
52         }
53         int ans=0;
54         for(int i=0; i<26; i++)
55         {
56             if(vis[i]&&f[i]==i)
57               ans++;
58         }
59         if(ans>1)
60         {
61             printf("The door cannot be opened.\n");
62             continue;
63         }
64         int m1=0,m2=0;
65         bool flag=true;
66         for(int j=0; j<26; j++)
67         {
68             if(vis[j]&&in[j]!=ou[j])
69             {
70                 if(in[j]-ou[j]==1)
71                 {
72                     m1++;
73                 }
74                 else if(ou[j]-in[j]==1)
75                 {
76                     m2++;
77                 }
78                 else flag=false;
79             }
80         }
81         if(flag&&((m1==0&&m2==0)||(m1==1&&m2==1)))
82         printf("Ordering is possible.\n");
83         else
84         printf("The door cannot be opened.\n");
85     }
86     return 0;
87 }