记录编号	395169	评测结果	AAAAAAAAAA
题目名称	[HAOI 2006]受欢迎的牛	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.118 s
提交时间	2017-04-15 10:17:23	内存使用	17.10 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 400000
using namespace std;
int low[N],dfn[N];
int stack[N],hea;
int instack[N];
int ji=1;
int in[N],out[N];
int belong[N];
int max(int x,int y)
{
    if(x>y)
      return x;
    else
     return y;
}
int min(int x,int y)
{
    if(x>y)
      return y;
    else
     return x;
}
struct haha
{
       int to,next;
}a[N];
int cnt=1,head[N];
int n,m;
int flag[N];
void add(int u,int v)
{
     a[cnt].to=v;
     a[cnt].next=head[u];
     head[u]=cnt++;
}
void tarjan(int now)
{
     low[now]=dfn[now]=ji;
     ji++;
     stack[++hea]=now;
     instack[now]=1;
     for(int v=head[now];v;v=a[v].next)
     {
             int i=a[v].to;
             if(dfn[i]==-1)
             {
                tarjan(i);
                low[now]=min(low[now],low[i]);
             }
             else
               if(instack[i])
                  low[now]=min(low[now],dfn[i]);
     }
     if(low[now]==dfn[now])
     {
       int temp;
       while(1)
       {
         temp=stack[hea--];
         belong[temp]=cnt;
         flag[cnt]++;
         //cout<<"temp="<<temp<<"  cnt="<<cnt<<endl;
         instack[temp]=0;
         if(temp==now)
         {
           break;
         }
       }
       cnt++;
     }
}
int ans;
int main()
{
    freopen("cow.in","r",stdin);
    freopen("cow.out","w",stdout);
    scanf("%d%d",&n,&m);
    memset(dfn,-1,sizeof(dfn));
    pos(i,1,m)
    {
      int x,y;
      scanf("%d%d",&x,&y);
      add(x,y);
    }
    pos(i,1,n)
     if(dfn[i]==-1)
       tarjan(i);
    pos(i,1,n)
    {
        for(int v=head[i];v;v=a[v].next)
        {
             int j=a[v].to;
             //cout<<"i="<<i<<"   j="<<j<<endl;
             if(belong[i]!=belong[j])
             {
               out[belong[i]]++;
               in[belong[j]]++;
             }
        }
    }   
    /*pos(i,1,n)
     cout<<"belong[i]="<<belong[i]<<"   i="<<i<<endl;*/
     int ha;
    pos(i,1,cnt-1)
      if(out[i]==0&&flag[i]!=0)
      {
        ans++;ha=i;
      }
       
    if(ans>=2)
      cout<<0;
    else
      cout<<flag[ha];
    //while(1);
    return 0;
}