记录编号	443048	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	玉带林中挂	是否通过	通过
代码语言	C++	运行时间	0.244 s
提交时间	2017-08-29 11:52:39	内存使用	11.00 MiB

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int MAXN=200005;
int n,m;
int Link[MAXN],len=0;
int flow[MAXN],rudu[MAXN],chudu[MAXN],q[5*MAXN];
int head=1,tail=0,ans=0,vis[MAXN];
struct edge{int y,next;}e[2*MAXN];
inline int read()
{
	char ch=getchar();int x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void insert(int x,int y)
{
	e[++len].next=Link[x];
	Link[x]=len;
	e[len].y=y;
	rudu[y]++;
	chudu[x]++;
}
void init()
{
	memset(vis,0,sizeof(vis));
	n=read();m=read();
	memset(flow,0,sizeof(flow));
	memset(rudu,0,sizeof(rudu));
	memset(chudu,0,sizeof(chudu));
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		vis[x]=1;vis[y]=1;
		insert(x,y);
	}
}
void work()
{
	for(int i=1;i<=n;i++)
		if(rudu[i]==0&&vis[i])
		{
			q[++tail]=i;
			flow[i]=1;
		}
	for(;head<=tail;head++)
	{
		int t=q[head];
		for(int i=Link[t];i;i=e[i].next)
		{
			flow[e[i].y]+=flow[t];
			rudu[e[i].y]--;
			if(!rudu[e[i].y])
				q[++tail]=e[i].y;
		}
	}
}
void outt()
{
	for(int i=1;i<=n;i++)
		if(!chudu[i]&&vis[i])
			ans+=flow[i];
	cout<<ans<<endl;
}
int main()
{
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	init();
	work();
	outt();
	fclose(stdin);
	fclose(stdout);
	return 0;
}