记录编号	408293	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	TARDIS	是否通过	通过
代码语言	C++	运行时间	0.201 s
提交时间	2017-05-24 10:58:39	内存使用	1.96 MiB

#include<bits/stdc++.h>
#define COGS
using namespace std;
const int maxn=100010;
vector<int> G[maxn];
int n,m,inde[maxn],outde[maxn],temp1,temp2,save[maxn],ans[maxn];
bool inque[maxn];
inline void in(){
	#ifdef COGS
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	#endif
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&temp1,&temp2);
		G[temp1].push_back(temp2);
		inde[temp2]++,outde[temp1]++;
	}
}
inline void deal(){
	queue<int> que;
	for (int i=1;i<=n;i++){
		save[i]=inde[i];
		if (inde[i]==0&&outde[i]){
			que.push(i);
			inque[i]=ans[i]=1;
		}
	}
	while (!que.empty()){
		int u=que.front();que.pop();inque[u]=0;
		int num=G[u].size();
		for (int i=0;i<num;i++){
			int to=G[u][i];
			ans[to]+=ans[u];
			inde[to]--;
			if (!inque[to]&&!inde[to]){
				que.push(to);
				inque[to]=1;
			}
		}
	}
}
inline void pr(){
	int num=0;
	for (int i=1;i<=n;i++){
		if (save[i]&&!outde[i]){
			num+=ans[i];
		}
	}
	printf("%d",num);
}
int Main(){
	in();
	deal();
	pr();
	return 0;
}
int main(){;}
int xlm=Main();