拓扑排序

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。

2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

拓扑排序最经典的算法是Kahn算法。

// deg是入度，在存图的时候需要录入数据
// A是排序后的数组
// n是点的数量
int deg[MAXN], A[MAXN];
bool toposort(int n)
{
    int cnt = 0;
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (deg[i] == 0)
            q.push(i);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        A[cnt++] = t;
        for (auto to : edges[t])
        {
            deg[to]--;
            if (deg[to] == 0) // 出现了新的入度为0的点
                q.push(to);
        }
    }
    return cnt == n;
}

有一道例题：CF510C Fox And Names

#include<bits/stdc++.h>
//#define LOCAL
#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0int))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define print(x) cout<<(x)<<'\n'
#define print_v(x) for (int iii = 0; iii < (x).size() - 1; ++iii) {cout << (x)[iii] << ' ';}cout << (x)[(x).size() - 1]<< '\n'
using namespace std;
#define mp make_pair
#define int  long long
const int inf = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 5e5 + 5;
string lexicographic = "abcdefghijklmnopqrstuvwxyz";
int dist[MAXN], pre[MAXN];
int head[MAXN];
set<int> vertex;
int deg[MAXN], A[MAXN];
int cnt = 1;
int n, m;


struct Edge {
    int from, to, w, next;
} edges[MAXN];

void add(int u, int v, int w) {//添加一条边u--v
    edges[cnt].to = v;
    edges[cnt].w = w;
    edges[cnt].next = head[u];
    head[u] = cnt++;
}


bool update(string s1, string s2) {
    auto minlen = min(s1.size(), s2.size());
    for (int i = 0; i < minlen; ++i) {
        if (s1[i] != s2[i]) {
            add(s1[i], s2[i], 0);
            vertex.insert(s1[i]);
            vertex.insert(s2[i]);
            deg[s2[i]]++;
            return true;
        }
    }
    if (s1.size() > s2.size())return false;
    return true;
}


bool toposort() {
    int cntt = 0;
    priority_queue<int, vector<int>, greater<>> q;
    for (auto v: vertex) {
        if (deg[v] == 0)
            q.push(v);
    }


    while (!q.empty()) {
        int t = q.top();
        q.pop();
        A[cntt++] = t;
        for (int i = head[t]; i != -1; i = edges[i].next) {
            int to = edges[i].to, w1 = edges[i].w;
            deg[to]--;
            if (deg[to] == 0)
                q.push(to);
        }
    }
    return cntt == vertex.size();
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("output.txt", "w", stdout);
    freopen("input.txt", "r", stdin);
#endif
    memset(head, -1, sizeof(head));
    cin >> n;
    string name1, name2;
    if (n == 1) {
        print(lexicographic);
        exit(0);
    }
    cin >> name1;

    for (int i = 1; i < n; ++i) {
        cin >> name2;
        if (!update(name1, name2)) {
            print("Impossible");
            exit(0);
        }
        name1 = name2;
    }

    if (toposort()) {
        for (int i = 0; i < vertex.size(); ++i) {
            cout << (char) A[i];
        }

    } else {
        print("Impossible");
        exit(0);
    }
    for (auto ch: lexicographic) {
        if (find(A, A + vertex.size(), ch) == A + vertex.size())cout << (char) ch;
    }
}