Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ID: bradyawn
- PROG: cf
- LANG: C++11
- */
- #include <iostream>
- #include <algorithm>
- #include <iomanip>
- #include <fstream>
- #include <vector>
- #include <string>
- #include <cmath>
- #include <map>
- #include <utility>
- #include <algorithm>
- #include <set>
- #include <ctime>
- #include <queue>
- #include <stack>
- //#define inf cin
- //#define outf cout
- using namespace std;
- bool vis[26]{};
- void cycle(vector<vector<int>> &top, int start, int cur, bool &check)
- {
- vis[cur] = true;
- if (cur == start)
- {
- check = true;
- return;
- }
- if (check)
- {
- return;
- }
- for(int i = 0; i < top[cur].size(); i++)
- {
- cycle(top, start, top[cur][i], check);
- }
- }
- void dfs(vector<vector<int>> &top, stack<int> &order, int cur)
- {
- vis[cur] = true;
- for (int i = 0; i < top[cur].size(); i++)
- {
- if (!vis[top[cur][i]]) dfs(top, order, top[cur][i]);
- }
- order.push(cur);
- }
- int main()
- {
- //ifstream inf("");
- //ofstream outf("");
- //cout << setprecision(10);
- int n;
- cin >> n;
- vector<vector<int>> top(26, vector<int>());
- string prev;
- cin >> prev;
- string now;
- for (int i = 1; i < n; i++)
- {
- // now.clear();
- cin >> now;
- bool found = false;
- for (int j = 0; j < min(now.size(), prev.size()); j++)
- {
- if (now[j] != prev[j])
- {
- top[prev[j]-97].push_back(now[j]-97); //prev indexed as int, now stored as char
- found = true;
- break;
- }
- }
- if (!found && now.size() < prev.size())
- {
- cout << "Impossible" << endl;
- return 0;
- }
- prev = now;
- }
- stack<int> order;
- bool impos = false;
- for (int i = 0; i < 26 && !impos; i++)
- {
- for (int j = 0; j < top[i].size() && !impos; j++)
- {
- if (!vis[i]) cycle(top, i, top[i][j], impos);
- }
- }
- if (impos)
- {
- cout << "Impossible" << endl;
- return 0;
- }
- for (int i = 0; i < 26; i++) vis[i] = false;
- for (int i = 25; i >= 0; i--)
- {
- if (!vis[i]) dfs(top, order, i);
- }
- while (!order.empty())
- {
- cout << char(order.top()+97);
- order.pop();
- }
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement