510C | FXJFXJ

Description

狐狸 Ciel 即将发表一篇关于 FOCS (狐狸操作计算机系统，读作 "狐狸")的论文。她听到一个传言：论文的作者列表总是按照 lexicographical 顺序排列。在查看了一些例子后，她发现有时并非如此。在一些论文中，作者姓名并不是按照正常意义上的 lexicographical 顺序排列的。但是，在对字母表中的字母顺序进行某些修改后，作者姓名的顺序就会变成lexicographical顺序，这是事实！她想知道，是否存在一种字母顺序，可以使她提交的论文中的姓名按照 lexicographical 顺序排列。如果有，你应该找出这样的顺序。

lexicographical 顺序的定义如下。当我们比较 \(s\) 和 \(t\) 时，首先要找到最左侧位置上的不同字符（\(s_{i} ≠ t_{i}\)） .如果没有这样的位置 (即 \(s\) 是 \(t\) 的前缀，反之亦然)，则最短字符串较少。否则，我们将根据字母表中的顺序比较字符 \(s_i\) 和 \(t_i\) 。

Input

第一行包含一个整数 \(n ( 1 ≤ n ≤ 100 )\)：名称数量。

接下来的每 \(n\) 行包含一个字符串 \(name_i ( 1 ≤ |name_i| ≤ 100 )\)，即第 \(i\) 个名称。每个名称只包含小写字母。所有名称均不同。

Output

如果存在这样的字母顺序，即所给名称按词典排序，则输出任何这样的顺序，作为字符'a'-'z'的排列 (即首先输出修改后字母表的第一个字母，然后是第二个字母，依此类推)。否则输出单词 Impossible

官方题解

首先让我们想一想 S < T 可以告诉我们什么：

假设 S = abcxyz T = abcuv。

根据定义，当且仅当 x < u 时，S < T。

因此，我们可以将条件 name 1 < name 2，name 2 < name 3... 转化为字母的顺序。

那么问题就变成了：我们是否有一个排列满足这些条件。实际上这是一个经典的拓扑排序问题。

这个任务的一个技巧是，如果我们有像 xy < x 这样的情况，那么就没有解决办法。这在预测试中并没有涉及。 :)

洛谷题解

一道拓扑排序裸题。
对于字典序前后相邻的两个字符串 \(a\) 和 \(b ， b\) 肯定不能是 \(a\) 的前缀，不然的话这个字典序就是错的，要输出 Impossible。

如果 \(a\) 不是 \(b\) 的前缀的话，那么 \(a\) 和 \(b\) 第一个不相同的字符我们分别称之为 \(c\) 和 \(d ， c\) 的优先级肯定是要比 \(d\) 高的，也就是 \(c\) 在答案中出现的位置一定是要比 \(d\) 靠前的。

看到这里你想到了什么? 拓扑排序! 没错，我们要在图中连一条从 \(d\) 到 \(c\) 的有向边，最后输出这张图的拓扑排序就好了，如果图有环就输出 Impossible。

代码

#include <bits/stdc++.h>
using namespace std;
int n, in[1145], cnt, ans[1145];
string s1, s2;
vector<int> e[1145];
queue<int> q;
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> s1;
    for (int i = 1; i < n; i++)
    {
        cin >> s2;
        int m = min(s1.size(), s2.size()), j;
        for (j = 0; j < m; j++)
        {
            if (s1[j] != s2[j])
            {
                int x = s1[j] - 'a', y = s2[j] - 'a';
                e[x].push_back(y);
                in[y]++;
                break;
            }
        }
        if (j >= m && s2.size() < s1.size())
        {
            cout<<"Impossible";
            return 0;
        }
        s1 = s2;
    }
    for (int i = 0; i <= 25; i++)
        if (!in[i])
            q.push(i);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        ans[++cnt] = x;
        for (auto a : e[x])
        {
            in[a]--;
            if (!in[a])
                q.push(a);
        }
    }
    if (cnt < 26)
        cout<<"Impossible";
    else
        for (int i = 1; i <= 26; i++)
            cout<<(char)(ans[i] + 'a'); 
}