受欢迎的牛——Tarjan

题目描述：
题目来源：河南省选2006
链接: POJ2186 http://poj.org/problem?id=2186 bzoj1051 http://www.lydsy.com/JudgeOnline/problem.php?id=1051

每一头牛的愿望就是变成一头最受欢迎的牛。现在有 N 头牛，给你 M 对整数(A,B)，表示牛A认为牛B受欢迎。这种关系是具有传递性的，如果 A 认为 B 受欢迎，B 认为 C 受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。
输入格式：
第一行两个数 N，M 。
接下来 M 行，每行两个数 A，B，意思是 A 认为 B 是受欢迎的（给出的信息有可能重复，即有可能出现多个 A，B）
输出格式：
输出一个整数，即有多少头牛被所有的牛认为是受欢迎的。如果没有满足这种条件的情况，输出“0”。
样例输入：
3 3
1 2
2 1
2 3
样例输出：
1
样例说明：
只有牛 3 是受到所有牛欢迎的。
数据范围：
10% 的数据：N≤20；M≤50
30% 的数据：N≤1000；M≤20000
70% 的数据：N≤5000；M≤50000
100% 的数据：N≤10000；M≤50000
题目分析：
Tarjan模板题。只需缩点后记录出度，当且仅当只有一个出度为0的点（实际可能是一个强连通分量），存在最受欢迎的牛，个数为强连通分量的大小。否则，没有最受欢迎的牛，输出0。
注：不懂Tarjan的可以看我的讲解：http://blog.csdn.net/qianguch/article/details/54710272
附代码：

#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<iomanip>
#include<cctype>
#include<set>
#include<map>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn=1e4+10;
const int maxm=5e4+10;
int top,tot,n,m,times,cnt,dfn[maxn],low[maxn];
int nxt[maxm],to[maxm],first[maxn],stack[maxn];
int pd[maxn],num[maxn],x,y,du[maxn],sum,bh;
bool  vis[maxn],insta[maxn];

void create(int x,int y)
{
    tot++;
    nxt[tot]=first[x];
    first[x]=tot;
    to[tot]=y;
}

void dfs(int u)
{
    times++;
    dfn[u]=times;
    low[u]=times;
    vis[u]=true;
    insta[u]=true;
stack[top++]=u;
for(int e=first[u];e;e=nxt[e])
    {
if(vis[to[e]]==false)
        {
            dfs(to[e]);
            low[u]=min(low[u],low[to[e]]);
        }
else
if(insta[to[e]]==true)
                low[u]=min(low[u],dfn[to[e]]);
    }
if(low[u]==dfn[u])
    {
        cnt++;
while(top>=1&&stack[top]!=u)
        {
            top--;
            insta[stack[top]]=false;
            pd[stack[top]]=cnt;
            num[cnt]++;//记录每个强连通分量的大小
        }
    }
}

int main()
{
//freopen("lx.in","r",stdin);

scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
    {
scanf("%d%d",&x,&y);
        create(x,y);
    }
for(int i=1;i<=n;i++)
if(vis[i]==false)
            dfs(i);

for(int i=1;i<=n;i++)
for(int e=first[i];e;e=nxt[e])
if(pd[i]!=pd[to[e]])
                du[pd[i]]++;//计算出度

for(int i=1;i<=cnt;i++)
    {
if(du[i]==0)//看有多少个出度为0
        {
            sum++;
            bh=i;
        }
    }
if(sum==1)
printf("%d",num[bh]);
else
printf("0");

return 0;
}