[文章目录]
Description
在一个有N(1<=N<=10,000)头牛的牛群中，给你M(1<=M<=50,000)个二元组(A,B),表示A认为B是受欢迎的。既然受欢迎是可传递的，那么如果A认为B受欢迎，B又认为C受欢迎,则A也会认为C是受欢迎的，哪怕这不是十分明确的规定。 你的任务是计算被所有其它的牛都喜欢的牛的个数。
tarjan，先缩点，再找；
不过怎么找就是一个问题了，第一遍我是将所有强连通分量直接到达的num[]++；最后看是否有一个强连通分量num[]=n；但是会有一种情况就是，有一个牛和大家都喜欢的牛不是直接相连，这样的话就会使题目解=0。
打完之后感觉巨耗脑细胞，然而只有50分；
实际上该怎么找一个强连通分量呢？应该记录每一个强连通分量的出度；如果有>1个强连通分量出度为0的话，他们两个就一定不能互相到达，无解；如果只有一个的话，显然除了它，每个强连通分量都能到达另一个强连通分量，最后都会汇入到这个强连通分量里。想想看。。。
所以脑细胞都。。。了
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
int z[11000],top;
int deep[11000],low[11000],belong[11000],sum[11000],tot;
bool inz[11000];
int h[11000],to[51000],nxt[51000],cnt;
int h2[11000],to2[51000],nxt2[51000],tot2,ans;
int a,b,fna,t,n,m,tmp,flag,c;
void add1(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=h[x];
h[x]=cnt;
}
void add2(int x,int y)
{
to2[++tot2]=y;
nxt2[tot2]=h2[x];
h2[x]=tot2;
}
void tarjan(int x)
{
inz[x]=1;
z[++top]=x;
deep[x]=low[x]=++tot;
for(int i=h[x];i;i=nxt[i])
{
if(!deep[to[i]])
{
tarjan(to[i]);
if(low[ to[i] ] <low[x])
low[x]=low[ to[i] ] ;
}
else if(inz[ to[i] ])
{
if(deep[ to[i] ]<low[x])
low[x]=deep[ to[i] ];
}
}
if(deep[x]==low[x])
{
ans++;
do
{
t=z[top--];
inz[t]=0;
sum[ans]++;
belong[t]=ans;
add2(ans,t);
}while(t!=x);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
add1(a,b);
}
for(int i=1;i<=n;i++)
{
if(!deep[i])
tarjan(i);
}
for(int i=1;i<=ans;i++)
{
tmp=0;
for(int j=h2[i];j;j=nxt2[j])
{
for(int k=h[ to2[j] ];k;k=nxt[k])
{
if(belong[to[k]]!=i)
{
tmp=1;
}
}
}
if(tmp!=1)
{
flag++;
c=i;
}
}
if(flag==1)
printf("%d",sum[c]);
else
printf("0");
return 0;
}