强连通缩下点，出度为0有多个答案为0，否则答案为出度为0的强连通分量中点的个数。
发现一道tarjan模板题，顺便复习一波tarjan
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #include<cmath> #include<map> #define ll long long using namespace std; const int maxn=500010,inf=1e9; struct poi{int x,too,pre;}e[maxn]; int n,m,x,y,tot,top,tott,color,ans,ansi; int lack[maxn],dfn[maxn],low[maxn],last[maxn],st[maxn],num[maxn],col[maxn],chu[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } void add(int x,int y){e[++tot].x=x;e[tot].too=y;e[tot].pre=last[x];last[x]=tot;} void tarjan(int x) { dfn[x]=low[x]=++tott;st[++top]=x;lack[x]=top; for(int i=last[x],too=e[i].too;i;i=e[i].pre,too=e[i].too) if(!dfn[too])tarjan(too),low[x]=min(low[x],low[too]); else if(!col[too])low[x]=min(low[x],dfn[too]); if(dfn[x]==low[x])for(num[++color]=top-lack[x]+1;top>=lack[x];top--)col[st[top]]=color; } int main() { read(n);read(m); for(int i=1;i<=m;i++) read(x),read(y),add(x,y); for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i); for(int i=1;i<=m;i++)if(col[e[i].x]!=col[e[i].too])chu[col[e[i].x]]++; for(int i=1;i<=color;i++)if(chu[i]==0)ans++,ansi=i; if(ans==1)printf("%d ",num[ansi]); else printf("0"); return 0; }