Advertisement
Guest User

My solution

a guest
Oct 15th, 2017
652
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.48 KB | None | 0 0
  1. /*
  2.  ID: bradyawn
  3.  PROG: cf
  4.  LANG: C++11
  5. */
  6. #include <iostream>
  7. #include <algorithm>
  8. #include <iomanip>
  9. #include <fstream>
  10. #include <vector>
  11. #include <string>
  12. #include <cmath>
  13. #include <map>
  14. #include <utility>
  15. #include <algorithm>
  16. #include <set>
  17. #include <ctime>
  18. #include <queue>
  19. #include <stack>
  20.  
  21. //#define inf cin
  22. //#define outf cout
  23.  
  24. using namespace std;
  25.  
  26. bool vis[26]{};
  27.  
  28. void cycle(vector<vector<int>> &top, int start, int cur, bool &check)
  29. {
  30.     vis[cur] = true;
  31.     if (cur == start)
  32.     {
  33.         check = true;
  34.         return;
  35.     }
  36.     if (check)
  37.     {
  38.         return;
  39.     }
  40.     for(int i = 0; i < top[cur].size(); i++)
  41.     {
  42.         cycle(top, start, top[cur][i], check);
  43.     }
  44. }
  45.  
  46. void dfs(vector<vector<int>> &top, stack<int> &order, int cur)
  47. {
  48.     vis[cur] = true;
  49.     for (int i = 0; i < top[cur].size(); i++)
  50.     {
  51.         if (!vis[top[cur][i]]) dfs(top, order, top[cur][i]);
  52.     }
  53.     order.push(cur);
  54. }
  55.  
  56. int main()
  57. {
  58.     //ifstream inf("");
  59.     //ofstream outf("");
  60.     //cout << setprecision(10);
  61.    
  62.    
  63.     int n;
  64.     cin >> n;
  65.    
  66.     vector<vector<int>> top(26, vector<int>());
  67.    
  68.     string prev;
  69.     cin >> prev;
  70.     string now;
  71.     for (int i = 1; i < n; i++)
  72.     {
  73. //        now.clear();
  74.         cin >> now;
  75.        
  76.         bool found = false;
  77.        
  78.  
  79.         for (int j = 0; j < min(now.size(), prev.size()); j++)
  80.         {
  81.             if (now[j] != prev[j])
  82.             {
  83.                 top[prev[j]-97].push_back(now[j]-97); //prev indexed as int, now stored as char
  84.                 found = true;
  85.                 break;
  86.             }
  87.         }
  88.    
  89.        
  90.        
  91.         if (!found && now.size() < prev.size())
  92.         {
  93.             cout << "Impossible" << endl;
  94.             return 0;
  95.         }
  96.        
  97.         prev = now;
  98.     }
  99.    
  100.     stack<int> order;
  101.    
  102.     bool impos = false;
  103.    
  104.     for (int i = 0; i < 26 && !impos; i++)
  105.     {
  106.         for (int j = 0; j < top[i].size() && !impos; j++)
  107.         {
  108.             if (!vis[i]) cycle(top, i, top[i][j], impos);
  109.         }
  110.     }
  111.    
  112.     if (impos)
  113.     {
  114.         cout << "Impossible" << endl;
  115.         return 0;
  116.     }
  117.    
  118.     for (int i = 0; i < 26; i++) vis[i] = false;
  119.    
  120.     for (int i = 25; i >= 0; i--)
  121.     {
  122.         if (!vis[i]) dfs(top, order, i);
  123.     }
  124.    
  125.     while (!order.empty())
  126.     {
  127.         cout << char(order.top()+97);
  128.         order.pop();
  129.     }
  130.    
  131.     cout << endl;
  132.    
  133.     return 0;
  134.    
  135. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement