1. 题意描述
一本字典中有 \(r\) \((1 \leq r \leq 10^6)\) 个单词，单词长度不超过 $10^3 $，所有字母都是小写英文字母，但字母排序不是按英文字母排序，求所有出现字母的一种排序，如果不存在，输出 "IMPOSSIBLE"。
2. 题目分析
由排序规则可知，对于字符串 \(s\) 和 \(t\)，\(s\) 排在 \(t\) 前面，必是一下两种情况之一：
- \(s\) 是 \(t\) 前缀。
- 设 \(s\) 和 \(t\) 第一个不同字符位置为 \(i\)，则 \(s_i\) 的顺序在 \(t_i\) 之前。
所以，如果存在字符串 \(s\) 和 \(t\)，\(s\) 排在 \(t\) 前面但 \(t\) 是 \(s\) 前缀，则无解；然后可以记录每个导致 \(s\) 排在 \(t\) 前面的每对字母，判断是否矛盾并求解。
但是这个的时间复杂度是极高的，于是想办法优化。实际上，只需要对比相邻两个字符串即可保证正确性。证明如下：
如果存在字符串 \(s\) 和 \(t\)，\(s\) 排在 \(t\) 前面但 \(t\) 是 \(s\) 前缀，且 \(s\) 和 \(t\) 不相邻，可能会有：
- \(s\) 后一个字符串是 \(s\) 前缀，且 \(t\) 是这个字符串前缀，可以判断无解。
- \(s\) 后一个字符串不是 \(s\) 前缀，且 \(t\) 是这个字符串前缀，用归纳法可以证明这种情况会出现矛盾。
- \(t\) 不是 \(s\) 后一个字符串的前缀，则在 \(s\) 后一个字符串和 \(t\) 必然存在一个位置，使两个字符串这个位置上的字符不同，但此时 \(s\) 后一个字符串这个位置的字符同时在 \(s\) 这个位置的字符之前和之后，就能推出无解。
如果存在字符串 \(s\) 和 \(t\)，\(s\) 排在 \(t\) 前面，\(t\) 不是 \(s\) 前缀，可能会有：
- \(s\) 和 \(t\) 相邻，直接得到关系。
- \(s\) 后一个字符串是 \(s\) 前缀，可推出无解。
- \(s\) 是 \(s\) 后一个字符串前缀，可归纳证明可有其它信息得到 \(s\) 和 \(t\) 能得到的信息。
- \(s\) 后一个字符串和 \(s\) 不互相为前缀，且 \(s\) 后一个字符串和 \(s\) 第一个不相同的位置不在 \(s\) 和 \(t\) 第一个不相同的位置之前，可归纳证明可有其它信息得到 \(s\) 和 \(t\) 能得到的信息。
- \(s\) 后一个字符串和 \(s\) 不互相为前缀，且 \(s\) 后一个字符串和 \(s\) 第一个不相同的位置在 \(s\) 和 \(t\) 第一个不相同的位置之前，归纳法可推出能得到 \(s\) 后一个字符串和 \(s\) 第一个不相同位置上的字符同时在 \(s\) 这个位置上的字符之前和之后，则能推出无解。
综上，所有不相邻的两个字符串，要么可以用其它条件推出无解，要么可以用其它条件推出这两个字符串看获得的信息。
对这些条件分析，只需要用 Floyd 算法求传递闭包，然后如果存在字符 \(i\) 在 \(i\) 前，则无解；否则每次选出一个不在所有未选择字符之前的数作为插入当前得到顺序开头，则最终可以得到正确顺序。
3. 示例代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005, T = N * N, M = 105, C = 30;
int n, k;
char s[T][M];
bool f[C][C], st[C], ins[C];
char res[C];
int main()
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; i ++ )
{
int p;
scanf("%d", &p);
for(int j = 1; j <= k; j ++ ) scanf("%s", s[p * k + j] + 1);
}
for(int i = 1; i <= n * k; i ++ )
{
if(i < n * k)
for(int j = 1; j < M; j ++ )
{
if(!s[i][j]) break; // s[i] 是 s[i + 1] 前缀
if(!s[i + 1][j]) // s[i + 1] 是 s[i] 前缀
{
puts("IMPOSSIBLE");
return 0;
}
if(s[i][j] != s[i + 1][j]) // s[i + 1] 和 s[i] 第一个不相同字符的位置是 j
{
f[s[i][j] - 'a' + 1][s[i + 1][j] - 'a' + 1] = true; // s[i][j] 在 s[i + 1][j] 之前
break;
}
}
for(int j = 1; s[i][j]; j ++ ) ins[s[i][j] - 'a' + 1] = true; // 找到出现的字符
}
for(int k = 1; k <= 26; k ++ ) // Floyd 求传递闭包
for(int i = 1; i <= 26; i ++ )
for(int j = 1; j <= 26; j ++ )
f[i][j] |= f[i][k] & f[k][j];
for(int i = 1; i <= 26; i ++ )
if(f[i][i]) // i 在 i 之前，无解
{
puts("IMPOSSIBLE");
return 0;
}
int cnt = 0;
for(int i = 1; i <= 26; i ++ ) cnt += ins[i];
for(int i = 1; i <= cnt; i ++ )
{
int c;
for(int j = 1; j <= 26; j ++ )
if(ins[j] && !st[j])
{
int p = 0;
for(int k = 1; k <= 26; k ++ )
p += !st[k] && f[j][k];
if(!p) // j 不在所有未选出的字符前面
{
c = j;
break;
}
}
st[c] = true;
res[cnt - i] = c + 'a' - 1;
}
puts(res);
return 0;
}