记录编号	254394	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	Cydiater	是否通过	通过
代码语言	C++	运行时间	0.169 s
提交时间	2016-04-25 13:06:19	内存使用	11.00 MiB

#include <iostream>
#include <cmath>
#include <ctime>
#include <iomanip>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <map>
using namespace std;
const int MAXN=200005;
int N,M,LINK[MAXN],len=0,flow[MAXN],indu[MAXN],outdu[MAXN],q[5*MAXN],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;
}
inline void insert(int x,int y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;indu[y]++;outdu[x]++;}
void init(){
	memset(vis,0,sizeof(vis));
	N=read();M=read();
	memset(flow,0,sizeof(flow));
	memset(indu,0,sizeof(indu));
	memset(outdu,0,sizeof(outdu));
	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(indu[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];
			indu[e[i].y]--;
			if(!indu[e[i].y])
				q[++tail]=e[i].y;
		}
	}
}
void outt(){
	for(int i=1;i<=N;i++)
		if(!outdu[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();
	return 0;
}