Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define endl "\n"
- vector <vector <int>> g(26,vector <int> (26,0));
- vector <vector <int>> col(26,vector <int> (26,0));
- vector <bool> used(26,0);
- vector <int> ans;
- bool dfs(int v)
- {
- col[v] = 1;
- for (auto to : g[v])
- {
- if (to == 0) continue;
- if (col[to] == 1) return true;
- if (col[to] == 0)
- {
- if (dfs(to)) return true;
- }
- }
- col[v] = 2;
- return false;
- }
- void TopSort(int v)
- {
- used[v] = 1;
- for (auto to : g[v])
- {
- if (to == 0) continue;
- TopSort(to);
- }
- ans.push_back(v);
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- int n;
- cin>>n;
- string s;
- cin>>s;
- for (int i = 1; i < n; i++)
- {
- int j = 0;
- string t;
- cin>>t;
- while (j < min(s.size(), t.size()) && s[j] == t[j])
- j++;
- if (j == t.size())
- {
- cout<<"Impossible"<<endl;
- return 0;
- }
- if (j == s.size())
- {
- t = s;
- continue;
- }
- g[s[j] - 'a'][t[j] - 'a'] = 1;
- }
- /*for (int i = 0; i < 26; i++){
- for (int j = 0; j < 26; j++)
- cout<<g[i][j]<<" ";
- cout<<endl;
- }*/
- for (int i = 0; i < 26; i++)
- if (col[i] == 0 && dfs(i))
- {
- cout<<"Impossible"<<endl;
- return 0;
- }
- for (int i = 0; i < 26; i++)
- if (used[i] == 0)
- {
- TopSort(i);
- i = 0;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement