拓扑排序 (重生之我是弱鸡的自传)

youhualiuh / 2024-07-16 / 原文

Fox And Names Codeforces

Codeforces Round 290 (Div. 2)的C题

题意:

Ciel 发表一个论文,听到一个传说,论文的作者列表总是按照 lexicographical 顺序排序的 
她想知道是否有这种拉丁字母顺序,让她提交的论文按照 lexicographical 顺序排序,如果有输出
'a' - 'z'的顺序,否则输出Impossible


lexicographical 顺序排序定义是 比较s 和 t的时候, 首先我们会发现最左边的位置有不同的字符
si != ti 如果没有这个位置(及s是t的前缀) 则s比t要短,否则 按照字母
顺序比较si 和 ti两个字符 

输入:
第一行包含一个整数 n ( 1 ≤ n ≤ 100 )：名称数。
下面每行 n 包含一个字符串 namei ( 1 ≤ |namei| ≤ 100 )。( 1 ≤ |namei| ≤ 100 )，
即第 i 个名称。每个名称只包含小写拉丁字母。所有名称均不同。

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

解释与说明：

分析:

对于字典序前后相邻的字符串s 和 t
[首先如果没有这个位置(及s是t的前缀) 且 s.size() < t.size() or 已经在公共长度中出现了t[i] != s[i],这个顺序就是t[i].push_back(s[i])]
也就是变相的就是如果从左遍历s 与 t两个公共长度上的值都相同,但是
s.size() > t.size() 说明了这个顺序定义就不满足了 
最后通过Toposort观察最后答案是不是等于26

结论+思路:
1- 当公共长度相同时,但是s.size() > t.size() Impossible
2- 遍历完成后通过拓扑排序将字母存入ans中,如果最后的ans的长度!=26说明我的 lexicographical 顺序是没有的

这里我将字母变成数字,这里也变相的节省了空间,在去遍历的时候观察条件1是不是满足,满足直接结束循环输出Impossible
通过链式前向星储存边,跑一边Toposort判断一下满足输出字母顺序否则输出Impossible

Code:

#include<bits/stdc++.h>
    
using namespace std;
const int N = 3e2 + 5, M = 1e2 + 5;
int n, indep[N];
string s, t;
int cnt = 1, head[N];

struct Edge {
    int to, next;
} edges[M];

void init () {
    for (int i = 0; i < N; i++) head[i] = -1; 
    for (int i = 0; i < M; i++) edges[i].next = -1;
}

void addedge (int from, int to) {
    edges[cnt] = {to, head[from]};
    head[from] = cnt++;
    indep[to]++;
}

vector <int> ans;

bool Toposort () {
    queue <int> q; 
    for (int i = 0; i < 26; i++) {
        if (!indep[i]) q.push(i);
    }
    while (!q.empty()) {
        int from = q.front(); q.pop();
        ans.push_back(from);
        for (int to = head[from]; ~to; to = edges[to].next) {
            if (--indep[edges[to].to] == 0) q.push(edges[to].to);
        }
    }
    return ans.size() == 26;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    init ();
    cin >> s;
    for (int i = 2; i <= n; i++) {
        cin >> t;
        int minlen = min(s.size(), t.size()), j = 0;
        for (j = 0; j < minlen; j++) {
            if (s[j] != t[j]) {
                addedge(int(s[j] - 'a'), int(t[j] - 'a'));
                break;
            }
        } 
        if (j >= minlen && s.size() > t.size()) {
            cout << "Impossible\n";
            return 0;
        }
        s = t;
    }
    if (Toposort()) for (int i : ans) cout << char(i + 'a');
    else cout << "Impossible\n";
    return 0;
}