记录编号	409625	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	皓芷	是否通过	通过
代码语言	C++	运行时间	0.253 s
提交时间	2017-05-28 19:28:33	内存使用	2.60 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define mysister
#define maxn 100001
using namespace std;
int n,m,u,v,ansa=0,in[maxn],out[maxn],w[maxn];
vector<int>b[maxn];
vector<int>ans;
queue<int>q;
int main()
{
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
	  scanf("%d%d",&u,&v);
	  b[u].push_back(v);
	  in[v]++;
	  out[u]++;
	}
	for(int i=1;i<=n;i++)
	{
	  if(in[i]==0&&out[i]!=0)
	  {
		q.push(i);
		w[i]=1;
	  }
	}
	while(!q.empty())
	{
	  int u=q.front();q.pop();
	  for(int i=0;i<b[u].size();i++)
	  {
		w[b[u][i]]+=w[u];
		in[b[u][i]]--;
		if(in[b[u][i]]==0)
		{
		  if(out[b[u][i]]==0)ans.push_back(b[u][i]);
		  else q.push(b[u][i]);
		}
	  }
	}
	for(int i=0;i<ans.size();i++)
	  ansa+=w[ans[i]];
	printf("%d",ansa);
	return 0;
}