UVa 10129单词（欧拉回路）

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1070

题意是输入n个单词，是否可以把所有这些单词排成一个序列，使得每个单词的第一个字母和上一个单词的最后一个字母相同。输入中可以有重复单词。

由于最后只需要判断是否能排成这样的一个序列，所以没有输入单词后，只需要把首尾字母保存下来，然后可以dfs深度递归。由于可能会有重复单词，在这里可以设一个times数组来记录单词所用的次数。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 int map[30][30];
 6 int times[30][30];
 7 int number;
 8 
 9 void dfs(int u,int v)
10 {
11     number++; 
12     for (int i = 0; i < 26; i++)
13     {
14         if (map[v][i]>0 && times[v][i] < map[v][i])
15         {
16             times[v][i]++;
17             dfs(v, i);
18         }
19     }
20 }
21 
22 int main()
23 {
24     char s[1005];
25     int t;
26     cin >> t;
27     while (t--)
28     {
29         int n,p;
30         cin >> n;
31         p = n;
32         memset(s, 0, sizeof(s));
33         memset(map, 0, sizeof(map));
34         int k = 0,u,v,l;
35         while (n--)
36         {
37             cin >> s;
38             u = s[0] - 'a';
39             l = strlen(s);
40             v = s[l - 1] - 'a';
41             map[u][v]++;
42         }
43         int flag;
44         for (int i = 0; i < 26; i++)
45         {
46             flag = 0;
47             for (int j = 0; j < 26; j++)
48             {
49                 if (map[i][j]>0)
50                 {
51                     number = 0;
52                     times[i][j]++;
53                     dfs(i,j);
54                     memset(times, 0, sizeof(times));
55                     if (number == p)  { flag = 1; break; }
56                 }
57             }
58             if (flag == 1) break;
59         }
60         if (flag == 0)  cout << "The door cannot be opened." << endl;
61         else cout << "Ordering is possible." << endl;
62     }
63     return 0;
64 }