poj 1386 有向图欧拉（回）路

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 const int N = 26;
 7 const int M = 1001;
 8 int f[N];
 9 int degree[N];
10 bool visit[N];
11 char word[M];
12 
13 int findf( int x )
14 {
15     if ( f[x] != x ) f[x] = findf(f[x]);
16     return f[x];
17 }
18 
19 void union_set( int x, int y )
20 {
21     x = findf(x), y = findf(y);
22     if ( x != y )
23     {
24         f[x] = y;
25     }
26 }
27 
28 bool judge() 
29 {
30     int cnt = 0;
31     for ( int i = 0; i < N; i++ )
32     {
33         if ( visit[i] && f[i] == i ) cnt++;
34     }
35     if ( cnt > 1 ) return false;
36     int p = 0, q = 0;
37     for ( int i = 0; i < N; i++ )
38     {
39         if ( degree[i] == 1 )
40         {
41             p++;
42         }
43         else if ( degree[i] == -1 )
44         {
45             q++;
46         }
47         else if ( degree[i] )
48         {
49             return false;
50         }
51     }
52     return p <= 1 && p == q;
53 }
54 
55 int main ()
56 {
57     int t;
58     scanf("%d", &t);
59     while ( t-- )
60     {
61         int n;
62         scanf("%d", &n);
63         for ( int i = 0; i < N; i++ ) f[i] = i;
64         memset( degree, 0, sizeof(degree) );
65         memset( visit, 0, sizeof(visit) );
66         for ( int i = 0; i < n; i++ )
67         {
68             scanf("%s", word);
69             int first = word[0] - ‘a‘, last = word[strlen(word) - 1] - ‘a‘;
70             degree[first]--;
71             degree[last]++;
72             visit[first] = visit[last] = true;
73             union_set( first, last );        
74         }
75         if ( judge() ) printf("Ordering is possible.\n");
76         else printf("The door cannot be opened.\n");
77     }
78     return 0;
79 }