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
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <cctype> using namespace std; typedef long long ll; typedef struct{ int v,_next; }Edge; Edge edge[200005]; int cnt=0,at[100005],ru[100005]={0},V,E,ans[100005]={0}; int q[100005],f=0,r=0; void (int _u,int _v){ edge[cnt].v=_v, ru[_v]++, edge[cnt]._next=at[_u], at[_u]=cnt++; } void init(){ scanf("%d%d",&V,&E); int i,j,u,v; memset(at,-1,sizeof(at)); for(i=0;i<E;i++) scanf("%d%d",&u,&v), addedge(u-1,v-1); } void solve(){ int Ans=0; for(int i=0;i<V;i++) if(!ru[i]&&at[i]!=-1) ans[i]=1,q[r++]=i; while(r-f){ int h=q[f++],i,_v; for(i=at[h];i!=-1;i=edge[i]._next){ _v=edge[i].v; ru[_v]--; ans[_v]+=ans[h]; if(!ru[_v]) q[r++]=_v; } } for(int i=0;i<V;i++) if(at[i]==-1) Ans+=ans[i]; printf("%dn",Ans); } int main(){ init(); solve(); return 0; }
|
近期评论