题目描述
使用传统字典序对单词进行排序的做法如下(摘自百度百科)。
先按照第一个字母,以 a,b,c,…,z 的顺序排列;如果第一个字母一样,那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长(比如,sigh 和 sight),那么把短者排在前。
自定义字典序是指重新规定 a∼z 的相对顺序,然后按照上述方法对单词进行排序。
给定 n 个单词在某种自定义字典序下的顺序,请你计算该自定义字典序中 a∼z 的相对顺序。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含一个由小写字母构成的字符串,表示一个单词。
所有单词两两不同,且按照自定义字典序的顺序给出。
输出格式
输出自定义字典序中 a∼z 的相对顺序,即一个 a∼z 的排列。
如果无解,则输出 Impossible。
如果答案不唯一,输出任意合理答案均可。
数据范围
前 6 个测试点满足 1≤n≤10。所有测试点满足 1≤n≤100,每个单词的长度 [1,100]。
样例1
3
rkvist
scankr
ameinaf
输出样例
bcdefghijklmnopqrsatuvwxyz
提供一种特殊样例
2
sigth
sigt
输出样例
Impossible
算法
(拓朴排序)
考虑相邻的两个串,相同长度下,遇到出现不同字母时,将排前面的字母和排后面的字母连一个边,排后面的字母的入度+1,如:
yahd
ysciahdghs
第一个不同的为:’a’和’s’,则’a’向’s’连一个边,’s’的入度+1
特殊情况考虑,较短的字符串是较长的字符串的字串,但排序的顺序不对
最后进行拓扑排序求序列,如果存入字母不足26个,则输出”Impossbile”
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int M = 100 + 10, N = M * 2;
int n;
string s[M];
int h[N], e[N], ne[N], idx;
int in[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void topsort()
{
queue<int> q;
queue<char> ans;
for (int i = 1; i <= 26; i ++)
if (!in[i]) q.push(i);
while (!q.empty())
{
int t = q.front();
q.pop();
char x = char(t - 1 + 'a');
ans.push(x);
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
in[j] --;
if (!in[j]) q.push(j);
}
}
// 存下的字母不足26
if (ans.size() < 26)
{
cout << "Impossible";
return ;
}
while (!ans.empty())
{
cout << ans.front();
ans.pop();
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> n;
for (int i = 1; i <= n; i ++) cin >> s[i];
for (int i = 2; i <= n; i ++)
{
int m = min(s[i].size(), s[i - 1].size()), j;
for (j = 0; j < m; j ++)
{
if (s[i][j] != s[i - 1][j])
{
add(s[i - 1][j] - 'a' + 1, s[i][j] - 'a' + 1);
in[s[i][j] - 'a' + 1] ++;
break;
}
}
// 特殊情况考虑,如sigh 和 sight,把sight的排在前面了,不符合规则
if (j == m && s[i - 1].size() > s[i].size())
{
cout << "Impossible" << '\n';
return 0;
}
}
topsort();
return 0;
}