1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 const int N=10010,M=50010; 5 const int novis=-1,over=1,nowvis=0; 6 int size,head[M],next[M],to[M]; 7 int head2[M],next2[M],to2[M]; 8 int low[N],dfn[N],flag[N],color[N],que[N],sum[N], 9     top,cnt,n,m,sig;10 void tarjan(),uni(int,int),dfs(int),rebuild();11 int find(),min(int,int);12 int main(){13     int ans,x,y;14     size=0;15     memset(head,0,sizeof(head));16     memset(head2,0,sizeof(head2));17     scanf("%d %d",&n,&m);18     for (int i=1;i<=m;i++){19         scanf("%d %d",&x,&y);20         uni(x,y);21     }22     tarjan();23     rebuild();24     ans=find();25     printf("%d",ans);26     return 0;27 }28 void uni(int x,int y){29     size++;30     next[size]=head[x];31     head[x]=size;32     to[size]=y;33 }34 void tarjan(){35     memset(flag,novis,sizeof(flag));36     memset(color,0,sizeof(color));37     memset(sum,0,sizeof(sum));38     sig=cnt=top=0;39     for (int i=1;i<=n;i++)40         if (flag[i]==novis) dfs(i);41 }42 void dfs(int x){43     que[++top]=x;44     flag[x]=nowvis;45     low[x]=dfn[x]=++sig;46     for (int e=head[x];e;e=next[e]){47         int v=to[e];48         if (flag[v]==novis){49             dfs(v);50             low[x]=min(low[x],low[v]);51         }52         else if (flag[v]==nowvis)53             low[x]=min(low[x],dfn[v]);54     }55     if (low[x]==dfn[x]){56         int t;cnt++;57         do{58             t=que[top--];59             color[t]=cnt;60             flag[t]=over;61             sum[cnt]++;62         }while (t!=x);63     }64 }65 void rebuild(){66     size=0;67     for (int u=1;u<=n;u++){68         for (int e=head[u];e;e=next[e]){69             int v=to[e];70             if (color[u]!=color[v]){71                 size++;72                 next2[size]=head2[color[u]];73                 head2[color[u]]=size;74                 to2[size]=color[v];75             }76         }77     }78 }79 int find(){80     int ans=0;81     for (int i=1;i<=cnt;i++)82         if (!head2[i]){83             if (ans) return 0;84             else ans=sum[i];85         }86     return ans;87 }88 int min(int x,int y){89     return x<y?x:y;90 }