最大食物链计数原题链接

题意：

     给你一个食物网，请求出这个食物网中最大食物链的数量。n代表物种的种类，m代表食物链有几条边，接下来m行，每行a，b代表被吃者a和捕食者b。

注：最大食物链，链的最左边和最右边的端点已经不能再扩展了，最左边的端点一定是食物链的最低层，最右边的端点一定是食物链的最高层。

做题思路：

     本题运用了两个知识点，1.累加法，2.拓扑排序。

     首先，累加法怎么引用于本题，这里做个假设图：

alt

//可能有点丑，不要在意

     题目要求我们求出食物链最大食物链的数量，通过图可以很轻易的得出，从最左端到最右端的链的数量是3。

即：

          1->2->4

          1->2->3->4

          1->3->4

     从左往右看，记录每个点到点的个数，会得到这样一张表：

点 通往该点的路径个数
1 0
2 1
3 2
4 3

     我们可以发现当前点的路径总数，是由它所连接的上一个点的路径总数相加得到的，这就是累加法。

     在了解完累加法后，我们开始写题，这里因为点的数据大小特别大，所以我们还需要要用到链式前向星用来存点。

const int N=1e6+10,mod=80112002;
int n,m; 
//ans记录最长食物链长度
//id为链式前向星的编号 
int ans=0,id=1;
int head[N],in[N],nums[N];

/*
  链式前向星的作用是存边 
  用蛇来比喻: 
  head数组为蛇头，用来记录当前的顶点，摸着蛇头就可以摸到蛇身
  edges数组为蛇身，一个edges[i]看作一块蛇骨
   1.edges[i].to记录它连接的下一个蛇骨 
   2.edges[i].next记录的是上一个蛇骨的编号
  id是蛇的关节连接，将蛇骨之间像缝衣物一样串起来 
  建立链式前向星的过程就是将蛇从尾开始一直建立到头 
*/

struct Edge{
	int to,next;
}edges[N];

//链式前向星初始化 
void init(){
	//因为需要判断是否是链式前向星的顶点，所以需要将点初始化为-1 
	for (int i=1;i<N;i++)
	{
		head[i]=-1; 
		edges[i].next=-1;
	}
}
//链式前向星记点 
void addedge(int from,int to)
{
	//记录当前点到达的下一个点和连接它的上一个编号 
	edges[id]={to,head[from]};
	//更新顶点的编号 
	head[from]=id++;
	//记录入度 
	in[to]++;
}

     了解完，链式前向星后，我们就可以写拓扑排序了这里和模板拓扑排序维二多出的点就是多了累加法和链式前向星。

//拓扑排序 
int topu(){
	queue<int>q;
	for (int i=1;i<=n;i++)
	{
		if (!in[i])
		{
			//比原拓扑排序多出了nums[i]=1;
			//当in[i]==0时，说明i处于食物链最低端，标记为起始 
			nums[i]=1;
			q.push(i);
		}
	}
	while(!q.empty())
	{
		int from=q.front();
		q.pop();
		//当head[from]==-1，说明该条链已经到顶点，计算该条链的累加总数 
		if (head[from]==-1)ans=(ans+nums[from])%mod;
		/*
			链式前向星的跑点，简易版bfs 
		 	首先，to当前点的编号，即从该编号开始回溯
			然后，~to为判断条件，代表到-1时停止，而-1是代表他们的定点
			最后，将to从当前点的编号变为上一个点的编号 
		*/ 
		for (int to=head[from];~to;to=edges[to].next)
		{
			//累加法，当前点的总数由上一个的累加得来 
			nums[edges[to].to]=(nums[edges[to].to]+nums[from])%mod;
			//倘若入度为0，放入下一个点 
			if (--in[edges[to].to]==0)q.push(edges[to].to);
		}
	}
	return ans;
}

     最后附上完整代码：

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+10,mod=80112002;
int n,m; 
//ans记录最长食物链长度
//id为链式前向星的编号 
int ans=0,id=1;
int head[N],in[N],nums[N];

/*
链式前向星的作用是存边 
用蛇来比喻: 
head数组为蛇头，用来记录当前的顶点，摸着蛇头就可以摸到蛇身
edges数组为蛇身，一个edges[i]看作一块蛇骨
 1.edges[i].to记录它连接的下一个蛇骨 
 2.edges[i].next记录的是上一个蛇骨的编号
id是蛇的关节连接，将蛇骨之间像缝衣物一样串起来 
建立链式前向星的过程就是将蛇从尾开始一直建立到头 
*/

struct Edge{
	int to,next;
}edges[N];

//链式前向星初始化 
void init(){
	//因为需要判断是否是链式前向星的顶点，所以需要将点初始化为-1 
	for (int i=1;i<N;i++)
	{
		head[i]=-1; 
		edges[i].next=-1;
	}
}
//链式前向星记点 
void addedge(int from,int to)
{
	//记录当前点到达的下一个点和连接它的上一个编号 
	edges[id]={to,head[from]};
	//更新顶点的编号 
	head[from]=id++;
	//记录入度 
	in[to]++;
}

//拓扑排序 
int topu(){
	queue<int>q;
	for (int i=1;i<=n;i++)
	{
		if (!in[i])
		{
			//比原拓扑排序多出了nums[i]=1;
			//当in[i]==0时，说明i处于食物链最低端，标记为起始 
			nums[i]=1;
			q.push(i);
		}
	}
	while(!q.empty())
	{
		int from=q.front();
		q.pop();
		//当head[from]==-1，说明该条链已经到顶点，计算该条链的累加总数 
		if (head[from]==-1)ans=(ans+nums[from])%mod;
		/*
			链式前向星的跑点，简易版dfs 
		 	首先，to当前点的编号，即从该编号开始回溯
			然后，~to为判断条件，代表到-1时停止，而-1是代表他们的定点
			最后，将to从当前点的编号变为上一个点的编号 
		*/ 
		for (int to=head[from];~to;to=edges[to].next)
		{
			//累加法，当前点的总数由上一个的累加得来 
			nums[edges[to].to]=(nums[edges[to].to]+nums[from])%mod;
			//倘若入度为0，放入下一个点 
			if (--in[edges[to].to]==0)q.push(edges[to].to);
		}
	}
	return ans;
}

int main()
{
	cin >>n>>m;
	init();
	for (int i=1;i<=m;i++)
	{
		int from,to;
		cin >>from>>to;
		addedge(from,to);
	}
	cout <<topu()<<"\n";
    return 0;
}