Advertisement
Guest User

Untitled

a guest
Feb 25th, 2017
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.46 KB | None | 0 0
  1. #include <iostream>
  2. #include <map>
  3. #include <set>
  4. #include <vector>
  5. #include <stack>
  6. #include <queue>
  7. #include <deque>
  8. #include <stdio.h>
  9. #include <cmath>
  10. #include <sstream>
  11. #include <algorithm>
  12. #include <iomanip>
  13.  
  14. #define ll long long
  15. #define mp make_pair
  16. #define pb push_back
  17. #define f first
  18. #define s second
  19. #define vi vector<int>
  20. #define vl vector<long long>
  21. #define sz size()
  22. #define x first
  23. #define y second
  24. #define pii pair<int, int>
  25. #define pll pair<ll, ll>
  26.  
  27.  
  28. using namespace std;
  29.  
  30. string a[1010];
  31. int T, n, st, ft, degin[100], degout[100], deleted[1010];
  32. vi g[1010];
  33. vector<pii> edges;
  34. char ch[30];
  35. stack<int> S;
  36. vector<string> words[100][100];
  37.  
  38. bool euler_check() {
  39.    
  40.     for(int i = 1; i <= 26; i++) {
  41.         if(degin[i] - degout[i] == 1) {
  42.             if(ft == 0) ft = i;
  43.             else return false;
  44.         } else if(degin[i] - degout[i] == -1) {
  45.             if(st == 0) st = i;
  46.             else return false;
  47.         }
  48.     }
  49.  
  50.     if((st == 0 && ft != 0) || (st != 0 && ft == 0)) return false;
  51.  
  52.     edges.pb(mp(ft, st));
  53.     g[ft].pb(edges.sz - 1);
  54.     words[ft][st].pb("###");
  55.  
  56.     return true;
  57. }
  58.  
  59. vi find_euler_path() {
  60.     S.push(st);
  61.     vi ans;
  62.  
  63.     while(!S.empty()) {
  64.         int v = S.top();
  65.         for(int i = 0; i < g[v].sz; i++) {
  66.             int ind = g[v][i];
  67.             int to = edges[ind].s;
  68.             if(!deleted[ind]) {
  69.                 S.push(to);
  70.                 deleted[ind] = 1;
  71.                 break;
  72.             }
  73.         }
  74.  
  75.         if(v == S.top()) {
  76.             S.pop();
  77.             ans.pb(v);
  78.         }
  79.     }
  80.  
  81.     return ans;
  82. }
  83.  
  84. void clear() {
  85.     for(int i = 1; i <= 1000; i++) {
  86.         g[i].clear();
  87.        
  88.     }
  89.  
  90.     for(int i = 1; i <= 26; i++) {
  91.         degin[i] = degout[i] = 0;
  92.         for(int j = 1; j <= 26; j++) {
  93.             words[i][j].clear();
  94.         }
  95.     }
  96.  
  97.     edges.clear();
  98.     st = ft = 0;
  99.  
  100. }
  101.  
  102. void solve(int cs) {
  103.     clear();
  104.  
  105.     scanf("%d", &n);
  106.  
  107.     for(int i = 1; i <= n; i++) {
  108.         scanf("%s", ch);
  109.         a[i] = ch;
  110.     }
  111.  
  112.  
  113.     for(int i = 1; i <= n; i++) {
  114.         edges.pb(mp(a[i][0] - 'a' + 1, a[i][a[i].sz - 1] - 'a' + 1));
  115.         g[a[i][0] - 'a' + 1].pb(edges.sz - 1);
  116.        
  117.  
  118.         degin[a[i][a[i].sz - 1] - 'a' + 1]++;
  119.         degout[a[i][0] - 'a' + 1]++;
  120.  
  121.         words[a[i][0]][a[i][a[i].sz - 1]].pb(a[i]);
  122.     }
  123.  
  124.     printf("Case %d: ", cs);
  125.  
  126.     if(!euler_check()) {
  127.         printf("No\n");
  128.         return;
  129.     }
  130.  
  131.     vi v = find_euler_path();
  132.     reverse(v.begin(), v.end());
  133.    
  134.     vector<string> ans;
  135.  
  136.     for(int i = 0; i < v.sz; i++) {
  137.         cout << char(v[i] + 'a' - 1) << " ";           
  138.     }
  139. }
  140.  
  141. int main() {
  142.     //freopen("", "r", stdin);
  143.     //freopen("", "w", stdout);
  144.     scanf("%d", &T);
  145.     for(int i = 1; i <= T; i++) {
  146.         solve(i);
  147.     }
  148.  
  149.     return 0;
  150. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement