蒟蒻的拓扑排序学习笔记

_masppy_ · 2023-07-13 10:02:43 · 个人记录

\text{例题引入}

蒟蒻（我）由于太菜了想要重新学习算法,现在有一些算法供他学习，但学习某些算法需要先掌握他的前置算法，请你帮蒟蒻规划一个可行的学习顺序

举个栗例子，假设我们现在有5个可选算法A,B,C,D,E，它们的前置课程分别为分别为：

如果我们做个图，它应该长这样：

在图中，我们以算法为点，当一个算法为另一个算法的前置算法时，就在两点间连一条有向边

显然，当一点入度为0时，就代表该课程没有需要学习的前置算法。由此，我们可以在每次选取可学习课程时，使它指向的点入度-1，同时将它推入队列，然后再次进行操作。

为了更直观的理解，我们模拟一下样例：

• 第一次操作，选取算法B,将算法D和E入度-1

• 第二次操作，发现算法D入度为零，选取，将算法A入度-1

• 第三次操作，发现算法A入度为零，选取，将算法E和C入度-1

• ......

伟大的算法，这使我的屁股脱落

总结一下基本操作：将入度为0的点入队，把该点指向的点入度-1，重复

这就是基本的拓扑排序，不过需要注意的是，进行拓扑有一个前提，就是必须有一个入度为0的点，也就是说只有 \color{Red}\colorbox{WHite}{有向无环图} 才能进行拓扑排序

\text{基础运用}

和例题的思路一样，不多说，直接上代码

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        while(1){
            int x;
            scanf("%d",&x);
            if(!x) break;
            edge[i].push_back(x);//连边
            f[x]++;//增加入度
        }
    }
    int l=0,r=0;
    for(int i=1;i<=n;i++){
        if(!f[i]) q[++r]=i;//入度为0的入队
    }

    while(l<r){
        int x=q[++l];
        int m=edge[x].size();
        for(int i=0;i<m;i++){
            int u=edge[x][i];
            f[u]--;//减入度，可理解为断边
            if(!f[u]) q[++r]=u;//入队
        }
    }

    for(int i=1;i<=n;i++){
        printf("%d ",q[i]);
    }
    return 0;
}

\color{Gold}\colorbox{WHITE}{P4017 最大食物链计数}

难以相信我是在打拓扑板子之前写的这道题

机房是一个复杂的生态系统，有 n 个oier，oier之间有m种捕食关系，每个关系包括生物x, y，指生物 x 捕食 y ，请求出最大食物链的数量

最大食物链的定义：最左端的生物是最低营养级，最右端是最高营养级

\color{Gold}\colorbox{WHITE}{SOLUTION}

板子+dp，转移方程极易：dp[i]=dp[i]+dp[fr]，代码如下：

    for(int i=1;i<=m;i++) if(!l[i]) q.push(i),dp[i]=1;

    while(!q.empty()){
        int fr=q.front();
        q.pop();
        m=edge[fr].size();
        if(!m) ans=(ans+dp[fr])%mod;
        for(int i=0;i<m;i++){
            int x=edge[fr][i];
            l[x]--;
            if(!l[x]) q.push(x);
            dp[x]=(dp[fr]+dp[x])%mod;
        }
    }