fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define pb(x) push_back(x)
  3. #define all(x) x.begin(), x.end()
  4. #define cout2(x, y) cout << x << " " << y <<  endl
  5. #define N 200004
  6. #define MAXE 400004
  7.  
  8. using namespace std;
  9.  
  10. int next[MAXE], to[MAXE], last[N], E;
  11.  
  12. void addEdge(int u, int v){
  13.  
  14.     next[E] = last[u], to[E] = v, last[u] = E++;
  15. }
  16.  
  17. string getNode(int node){
  18.  
  19.     string ans = "";
  20.     while(node > 0)ans += char(node%128), node /= 128;
  21.  
  22.     reverse(all(ans));
  23.     return ans;
  24. }
  25.  
  26. bool vis_edge[MAXE];
  27. string aux, res = "";
  28.  
  29. void solve(int u, int id){
  30.  
  31.     if(id == 0){
  32.  
  33.         aux = getNode(u);
  34.         res += aux;
  35.     }
  36.  
  37.     for(int e = last[u]; e != -1; e = next[e]){
  38.  
  39.         int v = to[e];
  40.         if(vis_edge[e])continue;
  41.  
  42.         vis_edge[e] = true;
  43.         aux = getNode(v);
  44.  
  45.         res += aux[1];
  46.         solve(v, 1);    
  47.     }
  48.  
  49. }
  50.  
  51. bool vis[N];
  52. int in[N], out[N];
  53.  
  54. void DFS(int u){
  55.  
  56.     if(vis[u])return;
  57.     vis[u] = true;
  58.  
  59.     for(int e = last[u]; e != -1; e = next[e]){
  60.  
  61.         int v = to[e];
  62.         DFS(v);
  63.     }
  64. }
  65.  
  66. int main(){
  67.  
  68.     int n;
  69.     while(cin>>n){
  70.  
  71.         string s;
  72.         int u, v;
  73.  
  74.         set<int>S;
  75.         memset(last, -1, sizeof last);
  76.         E = 0;
  77.  
  78.         for(int i = 0; i < n; i++){
  79.  
  80.             cin>>s;
  81.             u = s[0] * 128 + s[1];
  82.             v = s[1] * 128 + s[2];
  83.  
  84.             addEdge(u, v);
  85.  
  86.             S.insert(u);
  87.             S.insert(v);
  88.  
  89.             in[v]++;        
  90.             out[u]++;
  91.         }
  92.  
  93.         vector<int>nodes(all(S));
  94.  
  95.         int ip = 0, comp, ini;
  96.         for(int i = 0; i < nodes.size(); i++){
  97.  
  98.             if(!vis[nodes[i]])comp++, DFS(nodes[i]);
  99.             if(abs(in[nodes[i]] - out[nodes[i]]) == 1)ip++;
  100.             else if(in[nodes[i]] != out[nodes[i]])ip = 100; 
  101.             if(in[nodes[i]] - out[nodes[i]] == -1)ini = nodes[i];
  102.         }
  103.  
  104.         if(comp == 1 && (ip == 0 || ip == 2)){
  105.  
  106.             cout << "YES" << endl;
  107.             int nod;
  108.  
  109.             if(ip == 2)nod = ini;
  110.             else nod = nodes[0];
  111.  
  112.             solve(nod, 0);
  113.             cout << res << endl;    
  114.  
  115.  
  116.         }
  117.         else puts("NO");
  118.  
  119.     }
  120.  
  121. }
  122.  
  123.  
Success #stdin #stdout 0s 9288KB
comments (?)
stdin
copy 
5
aca
aba
aba
cab
bac
stdout
copy 
YES
abacaba
https://ideone.com/1RfNzu
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!