Advertisement
Guest User

Untitled

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