图 - 拓扑排序

· · 算法·理论

<目录

拓扑排序 \color{grey}\textsf{Top Sort}

有些时候，做事情是有条件的。
你只能学完 \sf 1+1=2 才知道能弄懂 \sf1+2=3 是怎么回事。
你只有先写下 int main() 才能写出拓扑排序。

但，如果这些事情的关系非常复杂，比如：

\def\n{\\\hline} \def\arraystretch{1.2} \begin{array}{|c|c|} \hline \sf事件&\sf前置事件\n \sf 1&\sf\varnothing\n \sf 2&\sf 1,3\n \sf 3&\sf\varnothing\n \sf 4&\sf 1,2\n \sf 5&\sf 1,4\n \sf 6&\sf 1,2,3 \n \end{array} \Huge\rArr\normalsize \begin{array}{cc} \sf 3\\ \darr&\searrow\\ \sf 6&\larr&\sf 2\\ \uarr&\nearrow&\darr\\ \sf 1&\rarr&\sf 4\\ \darr&\swarrow\\ \sf 5 \end{array}

这里，我们用有向图来表示事情之间的关系。
那么，我们应该按照怎样的顺序合法地做完整个事情呢？
拓扑排序就是求这样一个顺序的算法。

底层思想

就是把现在所有能做的全做了。

从入度为零的点下手，做完一个事情删掉一个点，同时更改入度。
非常简单。

不能忘我们的……

代码

最大食物链计数

给你一个食物网，你要求出这个食物网中最大食物链的数量。
这里的“最大食物链”，指的是生物学意义上的食物链，即最左端是不会捕食其他生物的生产者，最右端是不会被其他生物捕食的消费者。
由于这个结果可能过大，你只需要输出总数模上 80112002 的结果。 (没有环)

#include<cstdio>
#include<queue>
#include<vector>
using std::queue;
using std::vector;
queue<int> Search;
vector<int> G[5005];
int Ans[5005],In[5005],N,M,Fans;
int main()
{
    scanf("%d %d",&N,&M);
    int u,v;
    while(M--)
        scanf("%d %d",&u,&v),
        G[u].push_back(v),
        In[v]++;
    for(int i=1;i<=N;i++)
        if(In[i]==0)
            Search.push(i),Ans[i]=1;
    while(!Search.empty())
    {
        const int S=Search.front();
        const int I=G[S].size();
        Ans[S]%=80112002;
        bool End=true;
        for(int i=0;i<I;i++)
        {
            End=false;
            Ans[G[S][i]]+=Ans[S];
            Ans[G[S][i]]%=80112002;
            if(--In[G[S][i]]==0)
                Search.push(G[S][i]);
        }
        if(End) Fans+=Ans[S];
        Fans%=80112002;
        Search.pop();
    }
    printf("%d",Fans);
    return 0;
}

多提一嘴

拓扑排序不是唯一的。
如果 \sf 1 与 \sf 3 都可以现在做，那么先做 \sf 1 还是先做 \sf 3 就无所谓了。

拓扑排序也可以拿来判环。
如果事件已经成环了，说明这些事情都无法完成。
那么只用记录做了几件事，当算法结束时还有事没做，说明图里有环。

完结散花
怎么感觉有点水呢