1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
|
#include <cstdio> #include <cmath> #include <algorithm> #include <cstring> using namespace std; #define ll long long #define R register #define I inline template<class >void read( &x) { register ll c = getchar(), f = 1; x = 0; while(!isdigit(c)) {if (c == '-') f = -1; c = getchar();} while(isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f; } const int maxn=100100,maxm=200200; int dp[maxn],ind[maxn],outd[maxn]; struct edge { int v,c; edge *next; }*h[maxn],pool[maxm]; int tot; void addEdge(int u,int v) { edge *p=&pool[++tot]; p->v=v;p->next=h[u];h[u]=p; ind[v]++;outd[u]++; } void dfs(int u) { if(dp[u]) return ; if(outd[u]==0) { dp[u]=1; return ; } for(edge *p=h[u];p;p=p->next) { int v=p->v; dfs(v); dp[u]+=dp[v]; } } int n,m,ans; int main() { read(n);read(m); while(m--) { int u,v; read(u);read(v); addEdge(u,v); } for(int i=1;i<=n;i++) if(!ind[i] && outd[i]) dfs(i),ans+=dp[i]; printf("%dn",ans); return 0; }
|
近期评论