#include #include #include #include #include using namespace std; typedef long long ll; typedef long double ld; typedef pair ii; typedef vector vi; typedef vector vvi; typedef vector vii; #define x first #define y second #define pb push_back #define eb emplace_back #define rep(i,a,b) for(auto i=(a); i<(b); ++i) #define REP(i,n) rep(i,0,n) #define all(v) (v).begin(), (v).end() #define rs resize #define DBG(x) cerr << __LINE__ << ": " << #x << " = " << (x) << endl const ld PI = acos(-1.0); template using min_queue = priority_queue, greater>; template int sz(const T &x) { return (int) x.size(); // copy the ampersand(&)! } template ostream& operator<<(ostream &os, vector &v) { os << "\n["; for(T &x : v) os << x << ','; return os << "]\n"; } struct pairhash { public: template size_t operator()(const pair &p) const { size_t lhs = hash()(p.x); size_t rhs = hash()(p.y); return lhs ^ (rhs+0x9e3779b9+(lhs<<6)+(lhs>>2)); } }; struct SCC { int n, age=0, ncomps=0; vvi adj, comps; vi tidx, lnk, cnr, st; vector vis; SCC(vvi &_adj) : n(_adj.size()), adj(_adj), tidx(n, 0), lnk(n), cnr(n), vis(n, false) { for (ll i = 0; i < n; i++) { if (!tidx[i]) dfs(i); } } void dfs(int v) { tidx[v] = lnk[v] = ++ age; vis[v] = true; st.pb(v); for (int w : adj[v]) { if (!tidx[w]) dfs(w), lnk[v] = min(lnk[v], lnk[w]); else if (vis[w]) lnk[v] = min(lnk[v], tidx[w]); } if (lnk[v] != tidx[v]) return; comps.pb(vi()); int w; do { vis[w = st.back()] = false; cnr[w] = ncomps; comps.back().pb(w); st.pop_back(); } while (w != v); ncomps++; } }; void run() { ll n, m; cin >> n >> m; vvi adj(n); for (ll i = 0; i < m; i++) { ll a,b; cin >> a >> b; a--; b--; adj[a].pb(b); } SCC S(adj); vector source(S.ncomps, true); for (ll i = 0; i < n; i++) { for (ll j : adj[i]) { if (S.cnr[i] != S.cnr[j]) source[S.cnr[j]] = false; } } ll res = 0; for (bool b : source) { if (b) res++; } cout << res << endl; } signed main() { // DON'T MIX "scanf" and "cin"! ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(20); run(); return 0; }