首页 > 代码库 > POJ2186:Popular Cows
POJ2186:Popular Cows
.
#include <iostream>#include <string.h>#include <stdio.h>#include <algorithm>#define N 100002using namespace std;int n,m,tt,time,cnt,e,a[N],b[N],sum[N];struct node{ int x,y; int next;} eg[1000001];int head[N],low[N],dfn[N],f[N],instack[N],belong[N],s[N];void init(){ memset(head,-1,sizeof(head)); memset(instack,0,sizeof(instack)); memset(belong,0,sizeof(belong)); memset(sum,0,sizeof(sum)); memset(f,0,sizeof(f)); tt=0; cnt=0;}void add(int xx,int yy){ eg[tt].x=xx; eg[tt].y=yy; eg[tt].next=head[xx]; head[xx]=tt++;}void tarjan(int i){ int w; dfn[i]=low[i]=++time; instack[i]=1; s[++e]=i; for(int j=head[i]; j!=-1; j=eg[j].next) { w=eg[j].y; if(!dfn[w]) { tarjan(w); low[i]=min(low[i],low[w]); } else if(instack[w]==1) { low[i]=min(low[i],dfn[w]); } } if(dfn[i]==low[i]) { cnt++; do { w=s[e--]; instack[w]=0; belong[w]=cnt; } while(w!=i); }}void solve(){ time=e=0; memset(dfn,0,sizeof(dfn)); for(int i=1; i<=n; i++) { if(!dfn[i]) { tarjan(i); } }}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { init(); for(int i=1; i<=m; i++) { scanf("%d%d",&a[i],&b[i]); add(a[i],b[i]); } solve(); for(int i=1; i<=m; i++) { if(belong[a[i]]!=belong[b[i]]) { f[belong[a[i]]]=1; } } for(int i=1; i<=n; i++) { sum[belong[i]]++; } int V=0,count; for(int i=1; i<=cnt; i++) { if(!f[i]) { V++; count=sum[i]; } } if(V==1) printf("%d\n",count); else printf("0\n"); } return 0;}
POJ2186:Popular Cows
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。