Advertisement
Guest User

Untitled

a guest
Apr 8th, 2020
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.68 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define endl "\n"
  5. vector <vector <int>> g(26,vector <int> (26,0));
  6. vector <int> col(26,0);
  7. vector <bool> used(26,0);
  8. vector <int> ans;
  9.  
  10. bool dfs(int v)
  11. {
  12.     col[v] = 1;
  13.     for (int to = 0; to < 26; to++)
  14.     {
  15.         if (g[v][to] == 0)
  16.             continue;
  17.         if (col[to] == 1)
  18.             return true;
  19.         if (col[to] == 0)
  20.         {
  21.             if (dfs(to))
  22.                 return true;
  23.         }
  24.     }
  25.     col[v] = 2;
  26.     return false;
  27. }
  28.  
  29. void TopSort(int v)
  30. {
  31.     used[v] = 1;
  32.     for (int to = 0; to < 26; to++)
  33.     {
  34.         if (g[v][to] == 0 || used[to] == 1)
  35.             continue;
  36.         TopSort(to);
  37.     }
  38.     ans.push_back(v);
  39.  
  40. }
  41.  
  42. int main()
  43. {
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(nullptr);
  46.     cout.tie(nullptr);
  47.     int n;
  48.     cin>>n;
  49.     string s;
  50.     cin>>s;
  51.  
  52.     for (int i = 1; i < n; i++)
  53.     {
  54.         int j = 0;
  55.         string t;
  56.         cin>>t;
  57.         while (j < min(s.size(), t.size()) && s[j] == t[j])
  58.             j++;
  59.         if (j == t.size())
  60.         {
  61.             cout<<"Impossible"<<endl;
  62.             return 0;
  63.         }
  64.         if (j == s.size())
  65.         {
  66.             s = t;
  67.             continue;
  68.         }
  69.         g[s[j] - 'a'][t[j] - 'a'] = 1;
  70.  
  71.     }
  72.     for (int i = 0; i < 26; i++)
  73.         if (col[i] == 0 && dfs(i))
  74.         {
  75.             cout<<"Impossible"<<endl;
  76.             return 0;
  77.         }
  78.     for (int i = 0; i < 26; i++)
  79.         if (used[i] == 0)
  80.         {
  81.             TopSort(i);
  82.         }
  83.     reverse(ans.begin(),ans.end());
  84.     for (int i = 0; i < 26; i++)
  85.         cout<<(char) ('a' + ans[i]);
  86.  
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement