P4017

邻接表的记录 （但是教练的）

我的前向星

邻接表可以过，

前向星过不了！！！

#include <bits/stdc++.h>
#define int long long
#define f1(i,a,b) for(int i=a;i<=b;i++)
#define f2(i,a,b) for(int i=a;i>=b;i--)
#define ff(e,u) for(int e=h[u];e;e=nxt[e])
using namespace std;
const int N=1e5+5;
const int mod=80112002;
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+(int)(ch-'0');ch=getchar();}
	return x*f;
}

int h[N],to[N],nxt[N],w[N],in[N],out[N],cnt;

int add(int u,int v)
{
	to[++cnt]=v;
	nxt[cnt]=h[u];
	h[u]=cnt;
}
int n,m;
int ans=0;
int num[N];
void bfs()
{
	queue<int> q;
	int u,v;
	f1(i,1,n)
	{
		if(!in[i])
		{
			q.push(i);
			num[i]=1;
		}
	}	
	while(!q.empty())
	{
		u=q.front();q.pop();
		ff(e,u)
		{
			v=to[e];
			num[v]=(num[v]+num[u])%mod;
			in[v]--;
			if(!in[v])q.push(v);
		}
	}
	f1(i,1,n)if(!out[i])ans+=(num[i]%mod);
}
signed main()
{
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		int u=read();int v=read();
		add(u,v);
		in[v]++;out[u]++;
	}
	bfs();
	cout<<ans;
	return 0;
}