记录编号	442598	评测结果	AAAAAAAAAA
题目名称	[HAOI 2016]食物链	最终得分	100
用户昵称	Menamovic	是否通过	通过
代码语言	C++	运行时间	0.214 s
提交时间	2017-08-27 21:01:15	内存使用	30.83 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long ll;
const int maxn=400010;

ll head[4*maxn];
ll cnt=1;//按边编号从 1 开始 
ll in[maxn]={0},out[maxn]={0};
ll n,m;
ll sear[maxn];
ll ans=0;

struct Edge
{
	int u;
	int v;
	int next;
}edge[maxn*2];

inline void addedge(int u,int v)
{
    edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}

ll dfs(int u)
{
    if(sear[u]) return sear[u];
	ll ans=0;
    if(!out[u]&&in[u]) ans++;
    for(int i=head[u];i;i=edge[i].next)
	{
        int v=edge[i].v;
		ans+=dfs(v);
    }
    sear[u]=ans;
	return ans;
}

inline ll read()
{
    char ch='*';
    while(!isdigit(ch=getchar()));
    ll num=ch-'0';
    while(isdigit(ch=getchar())) num=num*10+ch-'0';
    return num;
}

int main()
{
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=m;i++)
	{
		int u,v;
        u=read();v=read();
		out[u]++;
		in[v]++;
        addedge(u,v);
    }
    for(int i=1;i<=n;i++)
	{
		if(!in[i]) ans+=dfs(i);
	}
    printf("%I64d",ans);
    return 0;
}