拓扑排序

· · 个人记录

基础概念

在一个有向图中，将所有点排序得到一个序列。对于任意点，使得所有指向它的点都在序列中比它提早出现，则该序列称为拓扑序列。

这么说不太好懂，举个栗子：

上图的拓扑序列是：4、1、3、2。

求拓扑序列的意义

当题目是求有向图（可能有环）中从 u 到 v 的不同路径时，我们可以求出它的拓扑序列，然后 DP 求解。

总之，求出有向图的拓扑序列，就能把它化为 DAG，便于求解。

拓扑排序

得到拓扑序列的算法称作拓扑排序，下面是主要思路：

首先，将入度为 0 的点加入队列，因为它们一定在序列开头。

然后遍历队列中的每个点，将它所指向的点的入度减 1，这样又得到一些入度为 0 的点，以此类推直到遍历完所有的点。

还是那张图，首先，把 4 加入队列，删去以它为发端的边：

此时 1 的入度又变为 0，重复上面的操作：

记录删点的次序，得到拓扑序列 4、1、3、2。

显然，遍历队列中点的次序不同，便会得到不同的拓扑序列，求出其一即可。

代码：

for(int i=1; i<=n;i++)
{
    if(ru[i]==0) 
    {
        q.push(i);
    }
}
for(int i=1; i<=n;i++)
{
    int u=q.front();
    topu[++cnt]=u;
    q.pop();
    for(int j=0; j<edge[u].size();j++)
    {
        int v=edge[u][j];
        ru[v]--;
        if(ru[v]==0) 
        {
            q.push(v);
        }
    }
}