思路
对于任意一对单词 $(w_i, w_j), i < j$,从左往后找到第一对不相同字母 $(c, d)$,由于 $w_i$ 的字典序小于 $w_j$,由定义 $c < d$。
c
wi --------|-----------
wj --------|---------
d
反之,若 $c < d$,则 $w_i < w_j$。即 $c < d$ 是 $w_i < w_j$ 的充要条件。
把字母看成点,若 $c < d$,则从 $c$ 连一条有向边到 $d$。枚举所有单词对,建立整张图。若该有向图有环,则存在一对字母 $c, d$,满足 $c < d$ 且 $d < c$,此时无解。否则,由拓扑序定义,图的任意拓扑序可以作为所有字母的相对顺序。
此外,可以证明只需通过相邻单词对建图,不相邻单词对中存在的边一定包含在相邻单词对中。以下只说明三个单词的情况,$n$ 个单词的情况可通过归纳法证明。
1. (s1, s2): x < y
(s2, s3): y < z
--> (s1, s3): x < z
------|-------- s1
x
------|-------- s2
y
------|-------- s3
z
2. (s1, s2): x < y
(s2, s3): m < n
--> (s1, s3): x < y
------|-------- s1
x
------|---|---- s2
y m
------|---|---- s3
y n
3. (s1, s2): x < y
(s2, s3): m < n
--> (s1, s3): m < n
---|---|------- s1
m x
---|---|------- s2
m y
---|----------- s3
n
#include <iostream>
#define NO_ANS { puts("Impossible"); return 0; }
using namespace std;
const int N = 110, M = 30;
int n;
string s[N];
bool g[M][M];
int d[M], q[M];
int hh = 0, tt = -1;
bool build(string& a, string& b) {
for (int i = 0; i < a.size() && i < b.size(); i++)
if (a[i] != b[i])
return g[a[i] - 'a'][b[i] - 'a'] = 1;
return a < b;
}
bool topsort() {
for (int i = 0; i < 26; i++)
if (!d[i])
q[++tt] = i;
while (hh <= tt) {
int t = q[hh++];
for (int i = 0; i < 26; i++)
if (g[t][i] && !--d[i])
q[++tt] = i;
}
return tt == 25;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> s[i];
for (int i = 1; i < n; i++)
if (!build(s[i - 1], s[i]))
NO_ANS
for (int i = 0; i < 26; i++)
for (int j = 0; j < 26; j++)
if (g[i][j])
d[j]++;
if (!topsort()) NO_ANS
else for (int i = 0; i <= tt; i++) putchar(q[i] + 'a');
return 0;
}