首页 > 代码库 > 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