【題解】Codeforces 510C. Fox And Names

【題目敘述】https://codeforces.com/problemset/problem/510/C
【解題想法】拓撲排序 (Topological sorting)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector <int> v[26];
vector <int> ans;
int n, in[26], now;
string s1, s2;
bool flag;

void func(string a, string b){
    int l = 0;
    while (l < min(a.size(), b.size())){
        if (a[l] != b[l]){
            v[a[l]-'a'].push_back(b[l]-'a');
            in[b[l]-'a']++;
            return;
        }
        l++;
    }
    if (b.size() < a.size()){
        flag = false;
    }
}

int main() {
    cin >> n;
    cin >> s1;
    flag = true;
    for (int i = 1; i < n; i++){
        cin >> s2;
        func(s1, s2);
        s1 = s2;
    }
    if (!flag) cout << "Impossible\n";
    else{
        queue <int> q;
        for (int i = 0; i < 26; i++){
            if (in[i] == 0) q.push(i);
        }
        while (!q.empty()){
            now = q.front();
            q.pop();
            ans.push_back(now);
            for (int i:v[now]){
                in[i]--;
                if (in[i] == 0)q.push(i);
            }
        }
        if (ans.size() != 26) cout << "Impossible\n";
        else{
            for (int i:ans){
                cout << char('a' + i);
            }
            cout << "\n";
        }
    }
}
分享本文 Share with friends