记录编号	392712	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	zChengYuan	是否通过	通过
代码语言	C++	运行时间	0.281 s
提交时间	2017-04-08 17:53:44	内存使用	2.60 MiB

#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("chain_2016.in");
ofstream fout("chain_2016.out");
int n,m;
vector<int> G[100010];
int d[100010];
int cd[100010];
int rd[100010];
int dp(int i);
int main()
{
	fin>>n>>m;
	int a,b;
	for(int i=0;i<m;++i)
	{
		fin>>a>>b;
		G[a].push_back(b);
		rd[b]=1;
		cd[a]=1;
	}
	int ans=0;
	for(int i=1;i<=n;++i)
	{
		if(rd[i]==0&&cd[i]!=0)ans+=dp(i);
	}
	fout<<ans<<endl;
}
int dp(int i)
{	
	if(d[i]>0)return d[i];
	if(cd[i]==0&&rd[i]!=0)return d[i]=1;
	for(int j=0;j<G[i].size();++j)
	{
		d[i]+=dp(G[i][j]);
	}
	return d[i];
}