POJ 1386 Play on Words （有向图欧拉路径判定）

 1 /* ***********************************************
 2 Author        :kuangbin
 3 Created Time  :2014-2-3 14:18:41
 4 File Name     :E:\2014ACM\专题学习\图论\欧拉路\有向图\POJ1386.cpp
 5 ************************************************ */
 6 
 7 #include <stdio.h>
 8 #include <string.h>
 9 #include <iostream>
10 #include <algorithm>
11 #include <vector>
12 #include <queue>
13 #include <set>
14 #include <map>
15 #include <string>
16 #include <math.h>
17 #include <stdlib.h>
18 #include <time.h>
19 using namespace std;
20 
21 int F[30];
22 int find(int x)
23 {
24     if(F[x] == -1)return x;
25     else return F[x] = find(F[x]);
26 }
27 void bing(int u,int v)
28 {
29     int t1 = find(u);
30     int t2 = find(v);
31     if(t1 != t2)F[t1] = t2;
32 }
33 char str[1010];
34 int in[30],out[30];
35 int main()
36 {
37     //freopen("in.txt","r",stdin);
38     //freopen("out.txt","w",stdout);
39     int T;
40     int n;
41     scanf("%d",&T);
42     while(T--)
43     {
44         scanf("%d",&n);
45         memset(F,-1,sizeof(F));
46         memset(in,0,sizeof(in));
47         memset(out,0,sizeof(out));
48         int s = -1;
49         while(n--)
50         {
51             scanf("%s",str);
52             int len = strlen(str);
53             int u = str[0] - ‘a‘;
54             int v = str[len-1] - ‘a‘;
55             bing(u,v);
56             out[u]++;in[v]++;
57             if(s == -1)s = u;
58         }
59         bool flag = true;
60         int cc1 = 0,cc2 = 0;
61         for(int i = 0;i < 26;i++)
62         {
63             if(out[i] - in[i] == 1)cc1++;
64             else if(out[i] - in[i] == -1) cc2++;
65             else if(out[i] != in[i])
66                 flag = false;
67             if(out[i] || in[i])
68                 if(find(i) != find(s))
69                     flag = false;
70         }
71         if( !( (cc1 == 0 && cc2 == 0) || (cc1 == 1 && cc2 == 1) ) )flag = false;
72         if(flag)printf("Ordering is possible.\n");
73         else printf("The door cannot be opened.\n");
74     }
75     return 0;
76 }