lg2863[USACO06JAN]牛的舞会 发表于 2018-03-31 | 分类于 算法 , 图论 , tarjan | 阅读数 次 链接:lg2863[USACO06JAN]牛的舞会 题解 tarjan模板 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=1e5;struct node{ int v,nxt; inline void init(int a,int b){v=a;nxt=b;}}e[N];int dfn[N],low[N],in[N],ans,cnt,head[N],n,m,stck[N],indx;inline void adde(int a,int b){ e[cnt].init(b,head[a]); head[a]=cnt++;}void tarjan(int u){ in[u]=1; low[u]=dfn[u]=++cnt; stck[++indx]=u; for(int i=head[u],v;i!=-1;i=e[i].nxt){ if(!dfn[v=e[i].v]){tarjan(v); low[u]=min(low[u],low[v]);} else if(in[v])low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ int k=0; do{ in[indx]=0; --indx; k++; }while(stck[indx+1]!=u); if(k>1)ans++; }}int main(){ scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); rep(i,1,m){ int x,y; scanf("%d%d",&x,&y); adde(x,y); //adde(y,x); } cnt=0; rep(i,1,n){ if(!dfn[i])tarjan(i); } printf("%d\n",ans); return 0;}