bzoj 4562: [Haoi2016]食物链（luogu 3183）（Pu2 2018.10.23）

简述题意：

如图所示为某生态系统的食物网示意图，据图回答第1小题现在给你n个物种和m条能量流动关系，求其中的食物链条数。物种的名称为从1到n编号M条能量流动关系形如a1 b1a2 b2a3 b3......am-1 bm-1am bm其中ai bi表示能量从物种ai流向物种bi,注意单独的一种孤立生物不算一条食物链

算法：记忆化搜索+dp

时间复杂度：

题解：

记录一个点的入度和出度

然后枚举每个点

如果这个点入度==0&&出度！=0（注意这一点，因为单个生物不合法，没加只能得20分）

进行dfs!

如果这个点出度为0（*）

然后将结果累加更新DP就行了

注意一些细节！见代码！

代码如下：

#include <bits/stdc++.h>
#define ll long long
#define N 100005 
using namespace std;
int dp[N];
struct node
{
	int next;
	int to;
}edg[N<<1];
int hea[N],cnt=1;
void init()
{
	memset(hea,-1,sizeof(hea));
	cnt=1;
}
void add(int u,int v)
{
	edg[cnt].next=hea[u];
	edg[cnt].to=v;
	hea[u]=cnt++;
}
int inr[N],our[N];
int dfs(int rt)
{
	if(dp[rt]) return dp[rt];
	if(!our[rt])
	{
		dp[rt]=1;
		return 1;
	}
	for(int i = hea[rt];i != -1;i=edg[i].next)
	{
		int to=edg[i].to;
		dfs(to);
		dp[rt]+=dp[to];	
	}
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	init();
	for(int i = 1;i <= m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		inr[y]++,our[x]++;
		add(x,y);
	}
	int ans=0;
	for(int i = 1;i <= n;i++)
	{
		if(!inr[i]&&our[i])
		{
			dfs(i);
			ans+=dp[i];
		}
	}
	printf("%d\n",ans);
	return 0 ;
}