P2341 [HAOI2006]受欢迎的牛

盛夏的果实

题意：
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶
牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜
欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你
算出有多少头奶牛可以当明星
个人认为，tarjan算法鼻祖题
今天复习了一遍，打了一遍
dfn即dfs的顺序
low记录的是能返回到最早遍历的祖先的dfn
缩点搞搞出度就行了
若有两个以上的点出度为0
无解。。。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define love_nmr 0
#define nmr 50505
#define olinr 10101
int n,m;
int dfn[olinr];
int low[olinr];
int ins[olinr];
int num;
int du[olinr];
int cnt;
int siz[olinr];
int head[olinr];
int tot;
int belong[olinr];
struct node
{
  int to,nxt;
}edge[nmr];
struct sta
{
  int ss[olinr];
  int tp;
  void pop()
  {
    tp--;
  }
  int top()
  {
    return ss[tp];
  }
  void push(int x)
  {
    tp++;
    ss[tp]=x;
  }
  bool empty()
  {
    if(!tp) return true;
    return false;
  }
}s;
inline int read()
{
  char ch=getchar();
  int f=1,x=0;
  while(!isdigit(ch))
  {
    if(ch=='-')
      f=-f;
    ch=getchar();
  }
  while(isdigit(ch))
  {
    x=(x<<1)+(x<<3)+(ch^48);
    ch=getchar();
  }
  return x*f;
}
inline void put(int x)
{
  if(x<0)
  {
    putchar('-');
    x=-x;
  }
  if(x>9)
    put(x/10);
  putchar(x%10+'0');
}
inline void tarjan(int x)
{
  s.push(x);
  ins[x]=true;
  dfn[x]=low[x]=++tot;
  for(int i=head[x];i;i=edge[i].nxt)
  {
    int go=edge[i].to;
    if(!dfn[go])
    {
      tarjan(go);
      low[x]=min(low[x],low[go]);
    }
    else if(ins[go])
      low[x]=min(low[x],dfn[go]);
  }
  if(dfn[x]==low[x])
  {
    int tp=0;
    num++;
    do
    {
      tp=s.top();
      s.pop();
      ins[tp]=false;
      belong[tp]=num;
      siz[num]++;
    }while(tp!=x);
  }
}
inline void add(int from,int to)
{
  cnt++;
  edge[cnt].to=to;
  edge[cnt].nxt=head[from];
  head[from]=cnt;
}
int main()
{
  n=read();
  m=read();
  int x,y;
  for(int i=1;i<=m;i++)
  {
    x=read();
    y=read();
    add(x,y);
  }  
  for(int i=1;i<=n;i++)
    if(!dfn[i])
      tarjan(i);
  for(int i=1;i<=n;i++)
    for(int j=head[i];j;j=edge[j].nxt)
    {
      int go=edge[j].to;
      if(belong[go]!=belong[i])
      {
        du[belong[i]]++;
      }
    }
  int ans=0;
  for(int i=1;i<=num;i++)
  {
    if(!du[i])
    {
      if(ans)
      {
        put(0);
        return 0;
      }
      ans=siz[i];
    }
  }
  put(ans);
  return 0;
}

----olinr