codeforces 508D . Tanya and Password 欧拉通路

题目链接

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

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

 #include <iostream>

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #include <map>

 #include <set>

 #include <stack>

 #include <string>

 #include <queue>

 using namespace std;

 #define pb(x) push_back(x)

 #define ll long long

 #define mk(x, y) make_pair(x, y)

 #define lson l, m, rt<<1

 #define mem(a) memset(a, 0, sizeof(a))

 #define rson m+1, r, rt<<1|1

 #define mem1(a) memset(a, -1, sizeof(a))

 #define mem2(a) memset(a, 0x3f, sizeof(a))

 #define rep(i, n, a) for(int i = a; i<n; i++)

 #define fi first

 #define se second

 typedef pair<int, int> pll;

 const double PI = acos(-1.0);

 const double eps = 1e-;

 const int mod = 1e9+;

 const int inf = ;

 const int dir[][] = { {-, }, {, }, {, -}, {, } };

 map <string, int> ma;

 string a[];

 int cnt, inde[], outde[], vis[*], num, ans[*], ecnt[];

 vector <int> v[];

 void dfs(int u) {

     while(ecnt[u]<v[u].size()) {

         dfs(v[u][ecnt[u]++]);

     }

     ans[num++] = u%;

 }

 int main()

 {

     ios::sync_with_stdio();

     string s, tmp;

     int n, pos1, pos2;

     cin>>n;

     int cnt = , start;

     for(int i = ; i<n; i++) {

         cin>>s;

         int u = *s[]+s[];

         int to = *s[]+s[];

         v[u].pb(to);

         inde[to]++;

         outde[u]++;

         start = u;

     }

     pos1 = -, pos2 = -;

     int flag = ;

     for(int i = ; i<; i++) {

         if(outde[i]!=inde[i]) {

             if(outde[i]==inde[i]+) {

                 if(pos1==-) {

                     pos1 = i;

                 }  else {

                     flag = ;

                 }

             } else {

                 if(pos2==-)

                     pos2=i;

                 else

                     flag = ;

             }

         }

     }

     if(flag||(pos1==-&&pos2!=-||pos2==-&&pos1!=-)) {

         cout<<"NO"<<endl;

         return ;

     }

     num = ;

     if(pos1 == -)

         pos1 = start;

     dfs(pos1);

     if(num != n+) {

         puts("NO");

         return ;

     }

     s = "", tmp = "";

     tmp = (char)(pos1/);

     for(int i = num-; i>=; i--) {

         tmp += char(ans[i]);

     }

     cout<<"YES"<<endl;

     cout<<tmp;

     return ;

 }