Tìm thứ tự bảng chữ cái để các từ được coi là đã sắp xếp trong C++

Cho mảng các từ, tìm thứ tự bảng chữ cái tiếng Anh bất kỳ sao cho các từ đã cho được coi là sắp xếp tăng dần, nếu tồn tại thứ tự như vậy, ngược lại trả về "impossible".

Ví dụ: từ = ["efgh", "wxyz"], kết quả "zyxvutsrqponmlkjihgfewdcba".

Các bước:

• ALPHABET = 26
• n = kích thước mảng
• Nếu n = 1, in "abcdefghijklmnopqrstuvwxyz" và trả về
• Tạo mảng kề adj[ALPHABET] và mảng in-degree in[ALPHABET] = 0
• pre = v[0]
• Với i từ 1 đến n-1: s = v[i]; tìm j đầu tiên mà s[j] != pre[j]; nếu j < min(|pre|,|s|) thì thêm cạnh pre[j] -> s[j] vào adj, tăng in[s[j]]; pre = s; continue; nếu |pre| > |s| thì in "Impossible" và trả về; pre = s
• Dùng stack my_stack: đẩy tất cả đỉnh có in-degree 0
• Mảng out lưu kết quả, mảng vis[26] = false
• Khi stack không rỗng: lấy x = top, pop; vis[x]=true; thêm x+'a' vào out; với mỗi đỉnh kề y của x: nếu vis[y] bỏ qua; giảm in[y]; nếu in[y]==0 đẩy y vào stack
• Nếu có đỉnh chưa thăm (vis[i]==false) in "Impossible"
• In các ký tự trong out

Ví dụ

#include <bits/stdc++.h>
using namespace std;
#define ALPHABET 26
void search_ordering(vector<string> v) {
    int n = v.size();
    if (n == 1) { cout << "abcdefghijklmnopqrstuvwxyz"; return; }
    vector<int> adj[ALPHABET];
    vector<int> in(ALPHABET, 0);
    string pre = v[0];
    for (int i = 1; i < n; ++i) {
        string s = v[i];
        int j;
        for (j = 0; j < min(pre.length(), s.length()); ++j)
            if (s[j] != pre[j]) break;
        if (j < min(pre.length(), s.length())) {
            adj[pre[j] - 'a'].push_back(s[j] - 'a');
            in[s[j] - 'a']++;
            pre = s;
            continue;
        }
        if (pre.length() > s.length()) {
            cout << "Impossible"; return;
        }
        pre = s;
    }
    stack<int> my_stack;
    for (int i = 0; i < ALPHABET; ++i) if (in[i] == 0) my_stack.push(i);
    vector<char> out;
    bool vis[26]; memset(vis, false, sizeof(vis));
    while (!my_stack.empty()) {
        char x = my_stack.top(); my_stack.pop();
        vis[x] = true;
        out.push_back(x + 'a');
        for (int i = 0; i < adj[x].size(); ++i) {
            if (vis[adj[x][i]]) continue;
            in[adj[x][i]]--;
            if (in[adj[x][i]] == 0) my_stack.push(adj[x][i]);
        }
    }
    for (int i = 0; i < ALPHABET; ++i) if (!vis[i]) { cout << "Impossible"; return; }
    for (int i = 0; i < out.size(); ++i) cout << out[i];
}
int main() {
    vector<string> v{"efgh", "wxyz"};
    search_ordering(v);
}

Đầu vào

{"efgh", "wxyz"}

Đầu ra

zyxvutsrqponmlkjihgfewdcba