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 <int> col(26,0);
- vector <bool> used(26,0);
- vector <int> ans;
- bool dfs(int v)
- {
- col[v] = 1;
- for (int to = 0; to < 26; to++)
- {
- if (g[v][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 (int to = 0; to < 26; to++)
- {
- if (g[v][to] == 0 || used[to] == 1)
- 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())
- {
- s = t;
- continue;
- }
- g[s[j] - 'a'][t[j] - 'a'] = 1;
- }
- 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);
- }
- reverse(ans.begin(),ans.end());
- for (int i = 0; i < 26; i++)
- cout<<(char) ('a' + ans[i]);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement