题目简述:n头奶牛,给出若干个欢迎关系a b,表示a欢迎b,欢迎关系是单向的,但是是可以传递的。另外每个奶牛都是欢迎他自己的。求出被所有的奶牛欢迎的奶牛的数目。
模型转换:N个顶点的有向图,有M条边(N≤10000,M≤50000)。求一共有多少个点,满足这样的条件:所有其它的点都可以到达这个点。
首先,这个题的N和M都非常大,硬做是肯定不行的。考虑如果这个图是一棵树,那么问题就变的很简单了,因为至多有一个点满足条件,这个点满足条件的充要条件是:这个点是树中唯一的出度为0的点。
那么我们能否把图转化为 有向无回路图DAG(感谢网友提出)呢?首先可以想到的是,如果图中包含有环,那么就可以把这个环缩成一个点,因为环中的任意两个点可以到达,环中所有的点具有相同的性质,即它们分别能到达的点集都是相同的,能够到达它们的点集也是相同的。那么是否只有环中的点才具有相同的性质呢?进一步的考虑,图中的每一个极大强连通分支中的点都具有相同的性质。所以,如果把图中的所有极大强连通分支求出后,就可以把图收缩成一棵树  DAG,问题就迎刃而解了。
预备知识:有向图的强连通分量的求法,这个和求割点的算法差不多。
算法框架:对有向图求强连通分量,然后找出所有独立的强连通分量(所谓独立,就是该连通分量里面的点到外面的点没有通路,当然,连通分量外的点是可以有路到强连通分量内的点的),如果独立的强连通分量的数目只有一个,那么,就输出这个强连通分量内解的个数,否则输出无解。
算法证明:
1:假设a和b都是最受欢迎的cow,那么,a欢迎b,而且b欢迎a,于是,a和b是属于同一个连通分量内的点,所有,问题的解集构成一个强连通分量。
2:如果某个强连通分量内的点a到强连通分量外的点b有通路,因为b和a不是同一个强连通分量内的点,所以b到a一定没有通路,那么a不被b欢迎,于是a所在的连通分量一定不是解集的那个连通分量。
3:如果存在两个独立的强连通分量a和b,那么a内的点和b内的点一定不能互相到达,那么,无论是a还是b都不是解集的那个连通分量,问题保证无解。
4:如果图非连通,那么,至少存在两个独立的连通分量,问题一定无解。

第一次用前向星存储图,在不方便开临街矩阵和临街表的情况下,用前向星存储边,再开一个数组存储开始和结束的位置,很方便。
#include<iostream>
using namespace std;
int n,m;
struct e
{
    
int a,b;
}edge[
50002];
int begin[10001],end[10001],ord[10001],belong[10001];//ord[]----按照dfs1逆序排列顶点,belong[]-----判断各点属于哪个分量
int order=0,indx=0;
bool noout[10001],v[10001];//noout----判断某强连通子图是否出度为0.
int cmp1(const void *p,const void *q)
{
    
struct e *c=(e *)p;
    
struct e *d=(e *)q;
    
return c->a>d->a?1:-1;
}
int cmp2(const void *p,const void *q)
{
    
struct e *c=(e *)p;
    
struct e *d=(e *)q;
    
return c->b>d->b?1:-1;
}
int dfs1(int t)
{
    
if(v[t])
        
return 0;
    v[t]
=1;
    
int i;
    
for(i=begin[t];i<=end[t];i++)
    {
        dfs1(edge[i].b);
    }
    ord[order
++]=t;
}
int dfs2(int t)
{
    
if(v[t])
        
return 0;
    v[t]
=1;
    
int i;
    
for(i=begin[t];i<=end[t];i++)
    {
        dfs2(edge[i].a);
    }
    belong[t]
=indx;
    
return 0;
}
int main()
{
    
int i,j;
    scanf(
"%d%d",&n,&m);
    
for(i=0;i<m;i++)
    {
        scanf(
"%d%d",&edge[i].a,&edge[i].b);
    }
    qsort(edge,m,
sizeof(edge[0]),cmp1);
    for(i=1;i<=n;i++)
    {
        begin[i]=1;
    }
    int pre=0;
    
for(i=0;i<=m;i++)
    {
        
if(edge[i].a!=pre)
        {
            begin[edge[i].a]
=i;
            end[pre]
=i-1;
            pre
=edge[i].a;
        }
    }//
处理数组下标
    memset(v,0,sizeof(v));
    
for(i=1;i<=n;i++)
    {
        dfs1(i);
    }
    qsort(edge,m,
sizeof(edge[0]),cmp2);
    for(i=1;i<=n;i++)
    {
        begin[i]=1;
    }
    pre=0;
    
for(i=0;i<=m;i++)
    {
        
if(edge[i].b!=pre)
        {
            begin[edge[i].b]
=i;
            end[pre]
=i-1;
            pre
=edge[i].b;
        }
    }
    memset(v,
0,sizeof(v));
    
for(i=order-1;i>=0;i--)
    {
        
if(!v[ord[i]])
        {
            indx
++;
            dfs2(ord[i]);
        }
    }
    memset(noout,
1,sizeof(noout)); 
    
for(i=0;i<m;i++)
    {
        
if(belong[edge[i].a]!=belong[edge[i].b])
        {
            noout[belong[edge[i].a]]
=0;
        }
    }
    
int sum=0,right;
    
for(i=1;i<=indx;i++)
    {
        
if(noout[i])
        {
            sum
++;
            right
=i;
        }
    }
    
if(sum==1)
    {
        sum
=0;
        
for(i=1;i<=n;i++)
        {
            
if(belong[i]==right)
                sum
++;
        }
        printf(
"%d\n",sum);
    }
    
else
        printf(
"0\n");
    
//system("pause");
    return 0;
}