图论 拓扑排序

QWQ 我一定要好好学图论

​​​​​​​​​​​​​​简单复述一下这篇博客的内容：什么是拓扑排序_ztenv的博客-CSDN博客_拓扑排序

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。

2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

举个例子：

1. 找出入度为0的节点，如有多个，输出序号较小的那个。
2. 输出后将此节点删除

 因此是1,2,3,4,5

数据结构：

• ru[]：入度
• chu[]：出度
• queue q：存储多个入度为0的节点

模板子题：最大食物链计数 - 洛谷

该题就是求路径总数，可以用拓扑排序的方法。相当于记录入度，并将入度的数量通过出度的边传给下一节点。

在建图的时候计算好入度和出度。

将所有入度为0的节点依次入队（保证顺序），并初始化链数为1。

对于出队节点：到达下一节点时更新链数，更新入度，以表示节点出队删除。

如果下一节点入度为0，将其加入队列，如果出度也为0，表示其为最后一个节点，size[i]就表示到达i的所有链数。因此加入总链数。

#include
#define MAXN 5005
#define MAXM 500000
//dfs+拓扑排序求路径和 
using namespace std; 
int Graph[MAXN][MAXN]={0};
int chu[MAXN],ru[MAXN],size[MAXN],ans=0;
queue q; 
int n,m;
int main(){
	cin>>n>>m;
	int eat,eaten;
	for(int i=0;i>eaten>>eat;
		Graph[eaten][eat]=1;
		chu[eaten]++;ru[eat]++;
	}
	for(int i=1;i<=n;i++)
	{
		//如果没有入度 ，就入队 
		if(!ru[i])
		{
			q.push(i);
			size[i]=1;//初始化链数
		}
	}
	
	while(q.size()!=0)
	{
		//弹出队首 
		int v=q.front();
		q.pop();
		for(int i=1;i<=n;i++)
		{
			if(Graph[v][i]==1)
			{
				size[i]+=size[v];//更新链数
				size[i]%=80112002;
				ru[i]--; //更新入度
				if(ru[i]==0)
				{
					if(chu[i]==0)
					{
						ans+=size[i];
						ans%=80112002;
						continue;
					}
					q.push(i);//将入度为0的节点加入队列 
				}
			 } 
		}
	}
	 cout<

模板题二：[NOIP2003 提高组] 神经网络 - 洛谷

比上一题略复杂，思路在注释中，比较好懂，23点卡了很久，因为边权有可能是0，因此需要手动memset一下设置不可达。，此外需要注意一下特判。

#include
#define MAXN 110
#define inf 999999999
using namespace std;
int n,p;
int c[MAXN],u[MAXN],g[MAXN][MAXN],sum[MAXN];
int chu[MAXN],ru[MAXN];
queue  q,o;
int main()
{
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	{
		cin>>c[i]>>u[i];
	}
	for(int i=1;i<=n;i++)//手动memset
    {
        for(int j=1;j<=n;j++)
        {
            g[i][j]=inf;
        }
    }
	for(int i=0;i>a>>b;
		cin>>g[a][b];
		//计算出度入度 
		chu[a]++;
		ru[b]++;
	}
	for(int i=1;i<=n;i++)
	{
		//记录输入层 
		if(ru[i]==0)q.push(i);
		//记录输出层 
		if(chu[i]==0)o.push(i);
	}
	//拓扑排序 
	while(q.size()!=0)
	{
		int v=q.front();
		q.pop();
		//对于出队节点，一般是前驱节点 
		for(int i=1;i<=n;i++)
		{
			//如果有后驱节点 
			if(g[v][i]!=inf)
			{
				//只有前驱节点c>0时会影响后驱节点 
				if(c[v]>0)sum[i]+=g[v][i]*c[v];
				ru[i]--;//入度-1。当入度为0时，说明不会有前驱节点影响该节点了 
				if(ru[i]==0)
				{
					//入队，更新c[i]，影响下一个节点 
					//cout<0)
		{
			cout< 
​​​​​​​