题目描述
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶
牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果A喜
欢B，B喜欢C，那么A也喜欢C。牛栏里共有N 头奶牛，给定一些奶牛之间的爱慕关系，请你
算出有多少头奶牛可以当明星。
输入输出格式
输入格式：
第一行：两个用空格分开的整数：N和M
第二行到第M + 1行：每行两个用空格分开的整数：A和B，表示A喜欢B
输出格式：
第一行：单独一个整数，表示明星奶牛的数量
输入输出样例
输入样例#1：
3 3
1 2
2 1
2 3
输出样例#1：
1
说明
只有 3 号奶牛可以做明星
【数据范围】
10%的数据N<=20, M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000
这道题考察的是Tarjan，Tarjan是什么，大家可以看这篇博客http://www.cnblogs.com/jason2003/p/8417629.html
首先，显而易见的是，只要一个强连通分量中一个奶牛是明星奶牛，那么这个强连通分量里面所有的奶牛都是明星奶牛，根据这个定理，我们可以忽视每一个奶牛，而是把这些奶牛的每一个连通分量建成一个点，然后所有的连通分量之间如果有边就将这两个连通分量连起来，我们可以得到下图
这样看来，最后的巫妖王阿尔萨斯就是明星奶牛的连通分量
其中，因为已经跑过Tarjan，所以剩下的点不存在连通分量，一般的点都有出边，但是最后的阿尔萨斯没有出边，所以这个点就是答案，这个点里面所有的点都是答案,但是，如果有两个点没有出边，就会比较悲惨：
麦迪文就会和阿尔萨斯打起来，这种情况就没有答案连通分量，也就是没有明星奶牛了，直接输出0.
附上代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>
using namespace std;
stack <int> S;
int total=;
int stamp=;
int num=;
int n,m;
int ans;
int flag=;
int dfn[],low[];
int head[],to[],next[];
int book[];
int point[];
int vis[];
int size[];
void adl(int a,int b)
{
total++;
to[total]=b;
next[total]=head[a];
head[a]=total;
return ;
}
void tarjan(int u)
{
stamp++;
dfn[u]=low[u]=stamp;
S.push(u);
vis[u]=;
for(int e=head[u];e;e=next[e])
{
if(!dfn[to[e]])
{
tarjan(to[e]);
low[u]=min(low[u],low[to[e]]);
}
else if(vis[to[e]])
low[u]=min(low[u],low[to[e]]);
}
if(low[u]==dfn[u])
{
num++;
int sum=;
while(!S.empty() && S.top()!=u)
{
sum++;
vis[S.top()]=;
point[S.top()]=num;
S.pop();
}
size[num]=sum;
vis[S.top()]=;
point[S.top()]=num;
S.pop();
}
}
int main()
{
cin>>n>>m;
for(int i=;i<=m;i++)
{
int a,b;
cin>>a>>b;
adl(a,b);
}
for(int i=;i<=n;i++)
if(!dfn[i])
tarjan(i);
for(int i=;i<=n;i++)
for(int e=head[i];e;e=next[e])
if(point[i]!=point[to[e]])
{
book[point[i]]=;
}
for(int i=;i<=num;i++)
if(book[i]==)
{
flag++;
ans=size[i];
}
if(flag>)
cout<<<<endl;
else
cout<<ans;
}