强连通分量：1309. [HAOI2006]受欢迎的牛
★★ 输入文件：cow.in 输出文件：cow.out 简单对比
时间限制：1 s 内存限制：128 MB
【题目描述】
每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛，给你M对整数（A，B），表示牛 A 认为牛
B受欢迎。这种关系是具有传递性的，如果A认为B受欢迎，B认为C受欢迎，那么牛A也认为牛C受欢迎。你的任务是求出有多少头牛被所有的牛认为是受欢迎的。
【输入格式】
第1行两个整数N，M；
接下来M行，每行两个数A，B，意思是A认为B是受欢迎的（给出的信息有可能重复，即有可能出现多个A，B）
【输出格式】
一个数，即有多少头牛被所有的牛认为是受欢迎的。
【样例输入】
3 3
1 2
2 1
2 3
【样例输出】
1
【数据范围】
10%的数据N<=20,M<=50
30%的数据N<=1000,M<=20000
70%的数据N<=5000,M<=50000
100%的数据N<=10000,M<=50000
/*判断能不能有“牛被所有的牛认为是受欢迎”，那就是缩点之后的图中出度为0的点只有一个，如果图中出度为0的点有多个，肯定不符合情况，找出该点之后，再输出该强连通分量即可*/
#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#include<stack>
#define N 10010
#define M 50010
bool in_stack[N];
int low[N],dfn[N],x,y,n,m,father[N];
int chudu[N],t=,topt=,head[N];
struct Edge{
int v,last,u;
}edge[M*];
stack<int>sta;
int ans[N],begi,en;
int read()
{
int sum=,ff=;
char s;
s=getchar();
while(s<''||s>'')
{
if(s=='-') ff=-;
s=getchar();
}
while(s>=''&&s<='')
{
sum=sum*+s-'';
s=getchar();
}
return sum*ff;
}
void add_edge(int u,int v,int k)
{
edge[k].u=u;
edge[k].v=v;
edge[k].last=head[u];
head[u]=k;
}
void input()
{
n=read();m=read();
for(int i=;i<=m;++i)
{
x=read();y=read();
add_edge(x,y,i);
}
}
void tarjan(int u)
{
low[u]=dfn[u]=++topt;
sta.push(u);
in_stack[u]=true;
for(int l=head[u];l;l=edge[l].last)
{
int v=edge[l].v;
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(in_stack[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
ans[++ans[]]=u;
int x;
do
{
x=sta.top();
sta.pop();
in_stack[x]=false;
father[x]=u;
}while(x!=u);
}
}
void suo_dian()
{
for(int l=;l<=m;++l)
{
if(father[edge[l].v]!=father[edge[l].u])
{
chudu[father[edge[l].u]]++;
}
}
}
int main()
{
freopen("cow.in","r",stdin);
freopen("cow.out","w",stdout);
input();
for(int i=;i<=n;++i)
{
if(!dfn[i])
{
tarjan(i);
}
}
suo_dian();
int sum=,l;
for(int i=;i<=ans[];++i)
if(chudu[ans[i]]==)
{
sum++;
l=ans[i];
}
if(sum>) printf("");
else if(sum==)
{
sum=;
for(int i=;i<=n;++i)
if(father[i]==l)
sum++;
printf("%d\n",sum);
}
fclose(stdin);fclose(stdout);
return ;
}