出处： Codeforces
主要算法：判环+拓扑
难度：4.2
思路分析：
要是把这道题联系到图上就很容易想了。
如何建图？由于最后要求名字满足字典序，所以不妨以字母为节点，然后按照题意的顺序从小的到大的连边。建图了又什么用？如果图存在环，那么也就意味着矛盾了——因为这比自己小的节点比自己大。因此是否存在一个合法的字典序的判断依据就是建的图是否存在环。
第二步，如何输出任意一个方案？这很简单，由于有可能有的字母根本没有参与建图，所以这些字母就不需要管了。对于在图里的字母，入度为0的点就是已知的应当最小的点——所以我们进行一次拓扑排序来得到序列。最后和其它字母拼合起来就好了。
代码注意点：
注意有两个相同前缀的字符串时，如果前面的那个字符串比后面的还要长，那么一定不满足，直接输出impossible就好了。因为无论字典序如何，都不可能满足前面的字典序比后面的小。
Code
/** This Program is written by QiXingZhi **/
#include <cstdio>
#include <queue>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define r read()
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int N = ;
const int INF = ;
inline int read(){
int x = ; int w = ; register int c = getchar();
while(c ^ '-' && (c < '' || c > '')) c = getchar();
if(c == '-') w = -, c = getchar();
while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar();
return x * w;
}
string s[N];
queue <int> q;
vector <int> G[];
bool exist[N],vis[N],b[N],hh[N];
int rd[N],Q[N],ans_topo[N];
int n,len1,len2,flg,_cur,t,topo_num;
inline void AddEdge(int u, int v){
exist[u] = ;
exist[v] = ;
G[u].push_back(v);
++rd[v];
}
inline void ThrowOut(){
printf("Impossible");
exit();
}
inline bool BFS(int x){
while(!q.empty()) q.pop();
q.push(x);
int cur,sz,to;
while(!q.empty()){
cur = q.front();
q.pop();
if(cur == _cur){
if(flg == -){
++flg;
}
else if(flg == ){
return ;
}
}
if(vis[cur]) continue;
vis[cur] = ;
sz = G[cur].size();
for(int i = ; i < sz; ++i){
to = G[cur][i];
q.push(to);
}
}
return ;
}
inline bool Check_Circle(){
for(int i = 'a'; i <= 'z'; ++i){
memset(vis,,sizeof(vis));
if(exist[i]){
_cur = i;
flg = -;
if(BFS(_cur)) return ;
}
}
return ;
}
int main(){
// freopen(".in","r",stdin);
cin >> n;
for(int i = ; i <= n; ++i){
cin >> s[i];
}
for(int i = ; i <= n; ++i){
len1 = s[i-].size();
len2 = s[i].size();
flg = ;
for(int j = ; j < len2; ++j){
if(j >= len1){
flg = ;
break;
}
if(s[i-][j] != s[i][j]){
flg = ;
AddEdge(s[i-][j],s[i][j]);
break;
}
}
if(flg == && len1 > len2){
ThrowOut();
}
}
if(Check_Circle() == ){
ThrowOut();
}
int flg=,sz;
for(;;){
flg = , t = ;
for(int i = 'a'; i <= 'z'; ++i){
if(rd[i] == && !b[i] && exist[i]){
flg = ;
b[i] = ;
Q[++t] = i;
}
}
if(!flg) break;
for(int i = ; i <= t; ++i){
int cur = Q[i];
ans_topo[++topo_num] = cur;
hh[cur] = ;
sz = G[cur].size();
for(int j = ; j < sz; ++j){
--rd[G[cur][j]];
}
}
}
for(int i = ; i <= topo_num; ++i){
printf("%c",ans_topo[i]);
}
for(int i = 'a'; i <= 'z'; ++i){
if(!hh[i]){
printf("%c",i);
}
}
return ;
}