算法学习笔记(53)： 拓扑排序

拓扑排序是对DAG（有向无环图）上的节点进行排序，使得对于每一条有向边 ， 都在 之前出现。简单地说，是在不破坏节点先后顺序的前提下，把DAG拉成一条链。如果以游戏中的科技树（虽然名字带树，其实常常不是树而只是DAG）举例，拓扑排序就是找到一种可能的点科技树的顺序。

拓扑排序最经典的算法是Kahn算法。首先，先拿出所有入度为0的点排在前面，并在原图中将它们删除：

这时有些点的入度减少了，于是再拿出当前所有入度为0的点放在已经排序的序列后面，然后删除：

因为是有向无环图，而且删除操作不会产生环，所以每时每刻都一定存在入度为0的点，一定可以不断进行下去，直到所有点被删除。

以下是一个 的实现（ 分别表示点数和边数），利用了队列：

// deg是入度，在存图的时候需要录入数据
// A是排序后的数组
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;
}

返回值为是否成功进行拓扑排序，也即是否存在环。也就是说拓扑排序是可以用来简单地判环的。有时会要求输出字典序最小的方案，这时把queue改成priority_queue即可，复杂度会多一个 。

这里有一道例题：

（CF510C Fox And Names）

Fox Ciel is going to publish a paper on FOCS (Foxes Operated Computer Systems, pronounce: "Fox"). She heard a rumor: the authors list on the paper is always sorted in the lexicographical order.
After checking some examples, she found out that sometimes it wasn't true. On some papers authors' names weren't sorted in lexicographical order in normal sense. But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!
She wants to know, if there exists an order of letters in Latin alphabet such that the names on the paper she is submitting are following in the lexicographical order. If so, you should find out any such order.
Lexicographical order is defined in following way. When we compare and , first we find the leftmost position with differing characters: . If there is no such position (i. e. is a prefix of or vice versa) the shortest string is less. Otherwise, we compare characters and according to their order in alphabet.
Input
The first line contains an integer ( ): number of names.
Each of the following n lines contain one string ( ), the -th name. Each name contains only lowercase Latin letters. All names are different.
Output
If there exists such order of letters that the given names are sorted lexicographically, output any such order as a permutation of characters 'a'–'z' (i. e. first output the first letter of the modified alphabet, then the second, and so on).
Otherwise output a single word "Impossible" (without quotes).
Examples
input
3
rivest
shamir
adleman
output
bcdefghijklmnopqrsatuvwxyz

简单地说，就是给出一张名字的列表，要找到一张字母表使得这张人名的列表是按字典序排列的。

通过对相邻的两个名字间进行比较，可以得到 个关系（如样例中 ， ），它们可以构成一张图，而最后线性的字母表也必须要满足这些关系。很明显，如果这张图存在环，必然是无解的；而如果无环，那么拓扑排序即可得到结果。