codeforces 508D . Tanya and Password 欧拉通路

给你n个长度为3的子串，这些子串是由一个长度为n+2的串分割得来的，求原串，如果给出的不合法，输出-1。

一个欧拉通路的题，将子串的前两个字符和后两个字符看成一个点，比如acb，就是ac->cb。然后建图。

 1 #include <iostream>
 2 #include <vector>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <cmath>
 7 #include <map>
 8 #include <set>
 9 #include <stack>
10 #include <string>
11 #include <queue>
12 using namespace std;
13 #define pb(x) push_back(x)
14 #define ll long long
15 #define mk(x, y) make_pair(x, y)
16 #define lson l, m, rt<<1
17 #define mem(a) memset(a, 0, sizeof(a))
18 #define rson m+1, r, rt<<1|1
19 #define mem1(a) memset(a, -1, sizeof(a))
20 #define mem2(a) memset(a, 0x3f, sizeof(a))
21 #define rep(i, n, a) for(int i = a; i<n; i++)
22 #define fi first
23 #define se second
24 typedef pair<int, int> pll;
25 const double PI = acos(-1.0);
26 const double eps = 1e-8;
27 const int mod = 1e9+7;
28 const int inf = 1061109567;
29 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
30 map <string, int> ma;
31 string a[400005];
32 int cnt, inde[400005], outde[400005], vis[400005*2], num, ans[2*400005], ecnt[66000];
33 vector <int> v[66000];
34 void dfs(int u) {
35     while(ecnt[u]<v[u].size()) {
36         dfs(v[u][ecnt[u]++]);
37     }
38     ans[num++] = u%256;
39 }
40 int main()
41 {
42     ios::sync_with_stdio(0);
43     string s, tmp;
44     int n, pos1, pos2;
45     cin>>n;
46     int cnt = 1, start;
47     for(int i = 0; i<n; i++) {
48         cin>>s;
49         int u = 256*s[0]+s[1];
50         int to = 256*s[1]+s[2];
51         v[u].pb(to);
52         inde[to]++;
53         outde[u]++;
54         start = u;
55     }
56     pos1 = -1, pos2 = -1;
57     int flag = 0;
58     for(int i = 1; i<66000; i++) {
59         if(outde[i]!=inde[i]) {
60             if(outde[i]==inde[i]+1) {
61                 if(pos1==-1) {
62                     pos1 = i;
63                 }  else {
64                     flag = 1;
65                 }
66             } else {
67                 if(pos2==-1)
68                     pos2=i;
69                 else
70                     flag = 1;
71             }
72         }
73     }
74     if(flag||(pos1==-1&&pos2!=-1||pos2==-1&&pos1!=-1)) {
75         cout<<"NO"<<endl;
76         return 0;
77     }
78     num = 0;
79     if(pos1 == -1)
80         pos1 = start;
81     dfs(pos1);
82     if(num != n+1) {
83         puts("NO");
84         return 0;
85     }
86     s = "", tmp = "";
87     tmp = (char)(pos1/256);
88     for(int i = num-1; i>=0; i--) {
89         tmp += char(ans[i]);
90     }
91     cout<<"YES"<<endl;
92     cout<<tmp;
93     return 0;
94 }