/* Tanjar缩点后 记好每个点属于第几个强联通分量 然后维护nu数组表示每个强联通分量的出度为几（枚举割边） 只要某个强联通分量有出度而没有入度 说明并不是多有牛都认为这里面的牛牛 最后找nu为零的唯一一个强联通分量 如果有好几个nu为零的 依旧没有符合条件的牛 即图并不连通 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 50010 using namespace std; int n,m,num,head[maxn],dfn[maxn],low[maxn],si,anss,nu[maxn]; int stack[maxn],top,f[maxn],tim,sum,belong[maxn],ans[maxn]; struct node { int u,v,pre; }e[maxn]; int init() { int x=0;char s;s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x; } void Add(int from,int to) { num++; e[num].u=from; e[num].v=to; e[num].pre=head[from]; head[from]=num; } void Tanjar(int s)//tarjan缩点 { dfn[s]=low[s]=++tim;//time为关键字... stack[++top]=s; f[s]=1; for(int i=head[s];i;i=e[i].pre) { if(dfn[e[i].v]==0)//还没有被访问过 即白点 { Tanjar(e[i].v); low[s]=min(low[s],low[e[i].v]);//可以用 low[e[i].v] 更新 low[s]（白色路径定理） } else if(f[e[i].v])//已经入栈 即是一条后向边用 dfn[e[i].v] 更新 low[s] low[s]=min(low[s],dfn[e[i].v]); } if(dfn[s]==low[s]) { sum++; while(stack[top]!=s) { ans[sum]++;f[stack[top]]=0; belong[stack[top]]=sum;top--; } ans[sum]++;f[stack[top]]=0; belong[stack[top]]=sum;top--; } } int main() { n=init();m=init(); int x,y; for(int i=1;i<=m;i++) { x=init();y=init(); Add(x,y); } for(int i=1;i<=n;i++) if(dfn[i]==0) Tanjar(i); for(int i=1;i<=n;i++) for(int j=head[i];j;j=e[j].pre) if(belong[i]!=belong[e[j].v]) nu[belong[i]]++;//统计出度 for(int i=1;i<=sum;i++) if(nu[i]==0) { si++; anss=ans[i]; } if(si==1)cout<<anss; else cout<<"0"; return 0; }