Advertisement
RaFiN_

euler for directed graph

Mar 16th, 2019
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. string s[MAX];map<string ,int >m;map<int,string>res;int cnt,o[MAX],in[MAX],pnt,flag,start;vi v[MAX],ans;
  2.  
  3. int check(string ss)
  4. {
  5.     if(m[ss]==0)
  6.     {
  7.         m[ss] = cnt;
  8.         res[cnt] = ss;
  9.         cnt++;
  10.     }
  11.     return m[ss];
  12. }
  13.  
  14. void again(int x)
  15. {
  16.     if(in[x]==o[x])return ;
  17.     else
  18.     {
  19.        /// cout<<abs(in[x]-o[x])<<" "<<res[x]<<endl;
  20.         if(abs(in[x]-o[x])>1)flag = 1;
  21.         else if(o[x]-in[x]==1)start = x,pnt++;
  22.         else pnt++;
  23.     }
  24. }
  25.  
  26. void dfs(int s)
  27. {
  28.     while(v[s].size())
  29.     {
  30.         int x = v[s][v[s].size() - 1];
  31.         v[s].pop_back();
  32.         dfs(x);
  33.     }
  34.     ans.pb(s);
  35. }
  36.  
  37.  
  38. int main()
  39. {
  40.     booster()
  41.     ///read("input.txt");
  42.     cnt = 1;
  43.     int n;
  44.     cin>>n;
  45.     for(int i = 0;i<n;i++)
  46.     {
  47.         cin>>s[i];
  48.         int x = check(s[i].substr(0,2));
  49.         int y = check(s[i].substr(1,2));
  50.         o[x]++;
  51.         in[y]++;
  52.         v[x].pb(y);
  53.     }
  54.     start = 1;
  55.     for(int i = 1;i<=cnt;i++)
  56.     {
  57.         again(i);
  58.     }
  59.     dfs(start);
  60.     if(flag||ans.size()!=n+1||pnt>2)cout<<"NO";
  61.     else
  62.     {
  63.         cout<<"YES";
  64.         cout<<endl;
  65.         reverse(all(ans));
  66.         for(int i = 0;i<ans.size();i++)
  67.         {
  68.             if(!i)cout<<res[ans[i]];
  69.             else cout<<res[ans[i]][1];
  70.         }
  71.     }
  72.  
  73.  
  74.     return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement