【拓补排序 TB_sort】P4017 最大食物链计数 升级版

P4017 最大食物链计数 链接此处

一句话题意

DAG拓补排序+累计方案数
只需要将求的值变为方案数就行

关键

1.依次遍历DAG图,要先找入度为0的点入队,接着用此点减小其他点入度,产生新的0入度后加入队列>>可以看做BFS变形

    for(int i=1;i<=n;i++) 
	if(to[i]==0) q.push(i),cnt[i]=1;//预处理:循环一遍,找出入度为0的点
    while(q.size())//处理条件:q.size()!=0,就是让每一个节点都入队后弹出
    {
        int u=q.front();q.pop();//取出
        for(auto v:e[u])//遍历所有指向节点
        {
            to[v]--;//入度减小
            cnt[v]=(cnt[v]+cnt[u])%mo;//食物链/方案 的数量=它已有方案数量+点u贡献方案数
			//ATTENSTION:取模类似cnt[v]+=cnt[u]时,一定要加起来取模以后再赋值!
            if(to[v]==0) q.push(v);//当此点0入度:就是前面的点全部处理完之后>>将此点加入队列
        }
    }

2.取模操作:取模类似a+=b%mo时,一定要加起来取模以后再赋值,写成a=(a+b)%mo的形式
cnt[v]+=cnt[u]%mo:是将cnt[u]取模后加在cnt[v]上,会溢出:如2e9+1e9% (1e9+7) =3e9
cnt[v]=(cnt[v]+cnt[u])%mo:万无一失:如(2e9+1e9)%1e9+7=1e9
3.小技巧:有时候拓补排序会用到原始入度,记得再开一个数组保存

知识版图

图的基操=>BFS=>DAG拓补排序=>统计方案类型