歐拉路的裸題???
1 #include <algorithm>
2 #include <iostream>
3 #include <cstring>
4 #include <cstdio>
5
6 using namespace std;
7
8 const int N = 3550;
9
10 int e[N][N], fir[4], a[N], m, tot, v[N], id[N], f[N], cnt = 0, ind[N], vec[N][N], l[N];
11 char s[3], sa[N];
12
13 inline bool cmp(int a, int b)
14 {
15 return sa[a] < sa[b];
16 }
17
18 void DFS(int u, int ste)
19 {
20 a[ste] = u;
21 if (ste == m)
22 {
23 for (int i = 0; i <= m; ++i) putchar(sa[a[i]]);
24 exit(0);
25 }
26 for (int i = 1; i <= tot; ++i)
27 if (e[u][i]) vec[u][++l[u]] = i;
28 sort(vec[u] + 1, vec[u] + 1 + l[u], cmp);
29 for (int i = 1; i <= l[u]; ++i)
30 {
31 if (!e[u][vec[u][i]]) continue;
32 e[u][vec[u][i]] = e[vec[u][i]][u] = 0;
33 DFS(vec[u][i], ste + 1);
34 e[u][vec[u][i]] = e[vec[u][i]][u] = 1;
35 }
36 }
37
38 int main()
39 {
40 scanf("%d", &m);
41 for (int i = 1; i <= m; ++i)
42 {
43 cin >> s[0] >> s[1];
44 if (!v[(int)s[0]]) v[(int)s[0]] = 1, id[(int)s[0]] = ++tot, sa[tot] = s[0];
45 if (!v[(int)s[1]]) v[(int)s[1]] = 1, id[(int)s[1]] = ++tot, sa[tot] = s[1];
46 e[id[(int)s[0]]][id[(int)s[1]]] = e[id[(int)s[1]]][id[(int)s[0]]] = 1;
47 ++ind[id[s[0]]], ++ind[id[s[1]]];
48 }
49 int ox = 0, ch = 0; fir[2] = 1;
50 for (int i = 1; i <= tot; ++i)
51 if (ind[i] & 1) ++ox, fir[ch ^ 1] = i, ch ^= 1;
52 else fir[2] = (sa[i] < (char)sa[fir[2]]) ? i : fir[2];
53 if (ox == 1 || ox > 2)
54 {
55 puts("No Solution");
56 return 0;
57 }
58 if (ox) { if (sa[fir[0]] > sa[fir[1]]) swap(fir[0], fir[1]); DFS(fir[0], 0); }
59 else { DFS(fir[2], 0); }
60 return 0;
61 }