#include using namespace std; const int N = 50002, M = N << 1; int n, m, ans; int stk[N], top; // tarjan算法需要用到的堆栈 bool in_stk[N]; // 是否在栈内 int dfn[N]; // dfs遍历到u的时间 int low[N]; // 从u开始走所能遍历到的最小时间戳 int ts; // 时间戳,dfs序的标识,记录谁先谁后 int id[N], scc_cnt; // 强连通分量块的最新索引号 int sz[N]; // sz[i]表示编号为i的强连通分量中原来点的个数 //链式前向星 int e[M], h[N], idx, w[M], ne[M]; void add(int a, int b, int c = 0) { e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++; } // tarjan算法求强连通分量 void tarjan(int u) { dfn[u] = low[u] = ++ts; stk[++top] = u; in_stk[u] = 1; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (!dfn[j]) { tarjan(j); low[u] = min(low[u], low[j]); } else if (in_stk[j]) low[u] = min(low[u], dfn[j]); } if (dfn[u] == low[u]) { ++scc_cnt; // 强连通分量的序号 int x; // 临时变量x,用于枚举栈中当前强连通分量中每个节点 do { x = stk[top--]; //弹出节点 in_stk[x] = false; //标识不在栈中了 id[x] = scc_cnt; //记录每个节点在哪个强连通分量中 sz[scc_cnt]++; //这个强连通分量中节点的个数+1 } while (x != u); } } int main() { memset(h, -1, sizeof h); scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int a, b; scanf("%d %d", &a, &b); add(a, b); } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i); //枚举结果数组,统计题目要求的 点数大于 1 的强联通分量个数 for (int i = 1; i <= scc_cnt; i++) if (sz[i] > 1) ans++; printf("%d\n", ans); return 0; }