记录编号	442588	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	Hyoi_iostream	是否通过	通过
代码语言	C++	运行时间	0.746 s
提交时间	2017-08-27 20:47:49	内存使用	3.56 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int u[200001],v[200001],summ[100001];//记忆搜索 
int first[100001],next[200001];//邻接表 
int sum=0,n,m;
bool a[100001],b[100001];//a表示有出边，b表示有边指向它 
inline void dfs(int x,int y){
	if(summ[x]!=0)
	   return;
	if(a[x]==0){
		summ[y]++; 
		//cout<<x<<endl;
		return;
	}
	int k=first[x];
	while(k!=0){
		dfs(v[k],x);
		summ[x]+=summ[v[k]];
		k=next[k];
	}
	if(y==0)
	    sum+=summ[x];
	return;
}
int main(){
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>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);//从最下面开始 
		}
	}
	cout<<sum;
	fclose(stdin);
	fclose(stdout);
	return 0;
}