寒假集训专题三 G.食物链

食物链

https://loj.ac/p/2060

题意

有n个物种，m条能量流动关系，求其中的食物链条数

思路

把他看成一项工程，完成顺序为从入度为0点开始到出度为0的点，求出从入到出的所有方案数。

首先用拓扑排序的思想，遍历入度到出度的所有点，给刚开始入度为0的点赋值为1，用记忆化的方法，在遍历的情况下更新每个结点的方法数，最后记录出度为0结点方法数的总和。

#include
using namespace std;
const int N= 1e5+7;
int n;
int in[N];
int out[N];
int shuz[N];
vector ans;
vector g[N]; 
vector ve;
void toupu()
{
	memset(shuz,0,sizeof(shuz));
	queue que;
	for(int i=1;i<=n;i++)
	{
		if(in[i]==0&&out[i]!=0)		//排除没有出度入度的
		{
			que.push(i);
			shuz[i]=1;
		}
		if(in[i]!=0&&out[i]==0)
		{
			ve.push_back(i);
		}
		 
	}
	while(que.size())
	{
		int u=que.front();que.pop();
		ans.push_back(u);
		for(int i=0;i>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		in[v]++;
		out[u]++;
	}
	toupu();
}