记录编号	332984	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	jjky	是否通过	通过
代码语言	C++	运行时间	1.345 s
提交时间	2016-10-29 17:23:52	内存使用	2.69 MiB

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<string.h>
#include<sstream>
#define MAXN 100005
#define MAXM 200005
using namespace std;
int head[MAXN],nc,n,m,in[MAXN],ans,used[MAXN],out[MAXN];
struct date
{
	int to,next;
};
date edge[MAXM];
void addedge(int a,int b)
{
	edge[nc].to=b;
	edge[nc].next=head[a];
	head[a]=nc++;
}
int dfs(int now)
{
	if(used[now]!=0)
		return used[now];
	int j,to;
	for(j=head[now];j!=-1;j=edge[j].next)
	{
		to=edge[j].to;
		used[to]=dfs(to);
		used[now]+=used[to];
	}
	return used[now];
}
int main()
{
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	int i,a,b;
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	for(i=1;i<=m;i++)
	{
		cin>>a>>b;
		addedge(a,b);
		in[b]=1;
		out[a]=1;
	}
	for(i=1;i<=n;i++)
		if(out[i]==0)
			used[i]=1;
	//for(i=head[1];i!=-1;i=edge[i].next)
	//	cout<<edge[i].to<<" ";
	for(i=1;i<=n;i++)
	{
		if(in[i]==0)
		{
			
			ans+=dfs(i);
			if(out[i]==0)
				ans--;
			//cout<<"ok dfs"<<endl;
		}
	}
	/*cout<<endl;
	for(i=1;i<=n;i++)
	{
		cout<<used[i]<<" "<<i<<endl;
	}
	*/
	
	cout<<ans<<endl;
	return 0;
}