老拓扑了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
#define fin(s) freopen(s".in","r",stdin)
#define I inline
using namespace std;
const int N=1e5+5,mod=998244353,G=3,W=mod-1;
template<class o>I void qr(o &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>I void qw(o x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
int in[N],out[N],f[N],q[N],n,m,l,r,id[N];
struct edge{int y,next;}a[N<<1];int len,last[N];
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;++in[y];++out[x];}
void top_sort()
{
l=1;r=0;int cnt=0;
for(int i=1;i<=n;i++)
if(!in[i])q[++r]=i,f[i]=1;
else if(!out[i])id[++cnt]=i;
for(int x=q[l];l<=r;++l,x=q[l])
for(int k=last[x],y;k;k=a[k].next)
{y=a[k].y;f[y]+=f[x];if(!(--in[y]))q[++r]=y;}
int ans=0;
for(int i=1;i<=cnt;i++)ans+=f[id[i]];
qw(ans);puts("");
}
int main()
{
qr(n),qr(m);
for(int i=1,x,y;i<=m;i++)
{
qr(x),qr(y);
ins(x,y);
}
top_sort();
return 0;
}
最后一次更新于2020-05-12
0 条评论