Advertisement
Guest User

Untitled

a guest
Apr 8th, 2020
189
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 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.  
  8. bool dfs(int v)
  9. {
  10.     col[v] = 1;
  11.     for (auto to : g[v])
  12.     {
  13.         if (to == 0) continue;
  14.         if (col[to] == 1) return true;
  15.         if (col[to] == 0)
  16.         {
  17.             col[to] = 1;
  18.             if (dfs(to)) return true;
  19.         }
  20.     }
  21.     return false;
  22. }
  23. int main()
  24. {
  25.     ios_base::sync_with_stdio(false);
  26.     cin.tie(nullptr);
  27.     cout.tie(nullptr);
  28.     int n;
  29.     cin>>n;
  30.     string s;
  31.     cin>>s;
  32.  
  33.     for (int i = 1; i < n; i++)
  34.     {
  35.         int j = 0;
  36.         string t;
  37.         cin>>t;
  38.         while (j < min(s.size(), t.size()) && s[j] == t[j])
  39.             j++;
  40.         if (j == t.size())
  41.         {
  42.             cout<<"Impossible"<<endl;
  43.             return 0;
  44.         }
  45.         if (j == s.size())
  46.         {
  47.             t = s;
  48.             continue;
  49.         }
  50.         g[s[j] - 'a'][t[j] - 'a'] = 1;
  51.  
  52.     }
  53.     /*for (int i = 0; i < 26; i++){
  54.         for (int j = 0; j < 26; j++)
  55.             cout<<g[i][j]<<" ";
  56.         cout<<endl;
  57.     }*/
  58.     for (int i = 0; i < 26; i++)
  59.         if (dfs(i)) cout<<"Impossible"<<endl;
  60.        
  61.  
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement