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 58 59 60
|
#include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm>
using namespace std; const int maxn=100010,maxm=500050; int edgecnt; struct { int v; node *next; }*h[maxn],pool[maxm]; void addEdge(int u,int v) { node *p=&pool[++edgecnt]; p->v=v;p->next=h[u];h[u]=p; } int idx,scc,dfn[maxn],low[maxn],bel[maxn],sta[maxn],top; bool ins[maxn]; void tarjan(int u) { dfn[u]=low[u]=++idx;sta[++top]=u;ins[u]=1; for(node *p=h[u];p;p=p->next) { int v=p->v; if(!dfn[v]) { tarjan(v); low[u]=min(low[u],low[v]); } else if(ins[v]) { low[u]=min(low[u],dfn[v]); } } if(dfn[u]==low[u]) { ++scc; do { bel[sta[--top]]=scc; ins[sta[top]]=false; }while(sta[top]!=u); } } int n,m,ans; int ind[maxn]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int a,b; scanf("%d%d",&a,&b); if(a!=b) addEdge(a,b); } for(int i=1;i<=n;i++) { if(!dfn[i]) tarjan(i); } for(int i=1;i<=n;i++) { for(node *p=h[i];p;p=p->next) { int v=p->v; if(bel[i]!=bel[v]) ind[bel[v]]++; } } for(int i=1;i<=scc;i++) if(ind[i]==0) ans++; printf("%dn",ans); return 0; }
|
近期评论