#include <bits/stdc++.h> using namespace std; const int N=10005; const int M=50005; int n, m, E=0, scc_cnt=0; int head[N], id[N], sz[N], dout[N]; int dfn[N], low[N], ts=0; // tarjan相关数组, dfn为时间戳数组, low为子树能够回溯到最早栈中节点的dfn值 stack<int> st; // tarjan 辅助栈 bool vis[N]; // 记录点是否在栈中 struct Edge{int v, ne;}e[M]; inline void add(int a, int b){ e[E].v=b; e[E].ne=head[a]; head[a]=E++; } void tarjan(int u){ // tarjan scc dfn[u]=low[u]=++ts; st.push(u); vis[u]=true; // 对u点的邻点进行tarjan递归 for(int i=head[u]; ~i; i=e[i].ne){ int v=e[i].v; if(!dfn[v]){ // 如果节点v未被访问, (u, v)为树枝边 tarjan(v); low[u]=min(low[u], low[v]); } else if(vis[v]){ // 如果节点被访问, (u, v)为后向边或者横叉边 low[u]=min(low[u], dfn[v]); } } if(low[u]==dfn[u]){ // 如果当前点是可以回溯到的最早点, 即scc的起点 ++scc_cnt; int j; do{ j=st.top(); st.pop(); vis[j]=false; id[j]=scc_cnt; sz[scc_cnt]++; }while(j!=u); } } int main(){ memset(vis, 0x00, sizeof vis); memset(id, 0x00, sizeof id); memset(sz, 0x00, sizeof sz); memset(dout, 0x00, sizeof dout); memset(head, -1, sizeof head); memset(dfn, 0x00, sizeof dfn); cin>>n>>m; for(int i=0; i<m; ++i){ int a, b; cin>>a>>b; add(a, b); } for(int i=1; i<=n; ++i){ // 对每个未访问的点做一次tarjan,找出所有的scc if(!dfn[i]) tarjan(i); } // 缩点统计出度 for(int i=1; i<=n; ++i){ for(int j=head[i]; ~j; j=e[j].ne){ int v=e[j].v; int a=id[i], b=id[v]; if(a!=b) dout[a]++; // 如果a和b不是一个scc, a的出度加1, 将scc a缩点处理 } } int cz=0, sum=0; for(int i=1; i<=scc_cnt; ++i){ if(!dout[i]){ cz++; sum+=sz[i]; if(cz>1){sum=0; break;} } } cout<<sum<<endl; return 0; }