记录编号	255735	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	O(1)	是否通过	通过
代码语言	C++	运行时间	0.242 s
提交时间	2016-04-28 18:21:24	内存使用	3.20 MiB

#include<cstdlib>
#include<fstream>
using namespace std;
int u[200001],v[200001],sumt[100001];//记忆搜索 
int first[100001],next[200001];//邻接表 
int sum=0,n,m;
bool a[100001],b[100001];//a表示有出边，b表示有边指向它 
ofstream fout("chain_2016.out");
ifstream fin("chain_2016.in");
void dfs(int x,int y)
{
	if(sumt[x]!=0)
	   return;
	if(a[x]==0)
	{
		sumt[y]++;
		//fout<<x<<endl;
		return;
	}
	int k=first[x];
	while(k!=0)
	{
		dfs(v[k],x);
		sumt[x]+=sumt[v[k]];
		k=next[k];
	}
	if(y==0)
	    sum+=sumt[x];
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	fin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		fin>>u[i]>>v[i];
		next[i]=first[u[i]];
		first[u[i]]=i;
		a[u[i]]=1;
		b[v[i]]=1;
	}
	for(int i=1;i<=n;i++)
	{
		if(b[i]==0&&a[i]==1)
		{
			dfs(i,0);
		}
	}
	fout<<sum;
	/*for(int i=1;i<=m;i++)
	{
		fout<<first[i]<<" "<<next[i]<<endl;
	}*/
}