记录编号	334989	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	Mealy	是否通过	通过
代码语言	C++	运行时间	0.599 s
提交时间	2016-11-01 20:16:12	内存使用	4.89 MiB

#include <iostream>
#include <cstdio>
#include <vector>


using namespace std;


const int nmax=200086;


int n,m;
int tmpfrom,tmpto;
int in[nmax]={0};
int out[nmax]={0};

int A[nmax]={0};


int ans=0;


vector<int > G[nmax];


void DFS(int tmpx,int tmpl)
{
	if(A[tmpx])
	{
		return;
	}
	if(out[tmpx]==0)
	{
		A[tmpl]++;
		return;
	}
	
	for(int i=0;i<G[tmpx].size();i++)
	{
		DFS(G[tmpx][i],tmpx);
		A[tmpx]+=A[G[tmpx][i]];
	}
	if(tmpl==0)
	{
		ans+=A[tmpx];
	}
}	


void PreDo()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		scanf("%d%d",&tmpfrom,&tmpto);
		in[tmpto]++;
		out[tmpfrom]++;
		G[tmpfrom].push_back(tmpto);
	}
	for(int i=1;i<=n;i++)
	{
		if(in[i]==0&&out[i]!=0)
		{
			DFS(i,0);
		}
	}
	printf("%d\n",ans);
}


int main()
{
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	PreDo();
	return 0;
}