題目簡(jiǎn)述：n頭奶牛，給出若干個(gè)歡迎關(guān)系a b，表示a歡迎b，歡迎關(guān)系是單向的，但是是可以傳遞的。另外每個(gè)奶牛都是歡迎他自己的。求出被所有的奶牛歡迎的奶牛的數(shù)目。
模型轉(zhuǎn)換：N個(gè)頂點(diǎn)的有向圖，有M條邊（N≤10000,M≤50000）。求一共有多少個(gè)點(diǎn)，滿(mǎn)足這樣的條件：所有其它的點(diǎn)都可以到達(dá)這個(gè)點(diǎn)。
首先，這個(gè)題的N和M都非常大，硬做是肯定不行的?？紤]如果這個(gè)圖是一棵樹(shù)，那么問(wèn)題就變的很簡(jiǎn)單了，因?yàn)橹炼嘤幸粋€(gè)點(diǎn)滿(mǎn)足條件，這個(gè)點(diǎn)滿(mǎn)足條件的充要條件是：這個(gè)點(diǎn)是樹(shù)中唯一的出度為0的點(diǎn)。
那么我們能否把圖轉(zhuǎn)化為樹(shù) 有向無(wú)回路圖DAG（感謝網(wǎng)友提出）呢？首先可以想到的是，如果圖中包含有環(huán)，那么就可以把這個(gè)環(huán)縮成一個(gè)點(diǎn)，因?yàn)榄h(huán)中的任意兩個(gè)點(diǎn)可以到達(dá)，環(huán)中所有的點(diǎn)具有相同的性質(zhì)，即它們分別能到達(dá)的點(diǎn)集都是相同的，能夠到達(dá)它們的點(diǎn)集也是相同的。那么是否只有環(huán)中的點(diǎn)才具有相同的性質(zhì)呢？進(jìn)一步的考慮，圖中的每一個(gè)極大強(qiáng)連通分支中的點(diǎn)都具有相同的性質(zhì)。所以，如果把圖中的所有極大強(qiáng)連通分支求出后，就可以把圖收縮成一棵樹(shù) DAG，問(wèn)題就迎刃而解了。
預(yù)備知識(shí)：有向圖的強(qiáng)連通分量的求法，這個(gè)和求割點(diǎn)的算法差不多。
算法框架：對(duì)有向圖求強(qiáng)連通分量，然后找出所有獨(dú)立的強(qiáng)連通分量（所謂獨(dú)立，就是該連通分量里面的點(diǎn)到外面的點(diǎn)沒(méi)有通路，當(dāng)然，連通分量外的點(diǎn)是可以有路到強(qiáng)連通分量?jī)?nèi)的點(diǎn)的），如果獨(dú)立的強(qiáng)連通分量的數(shù)目只有一個(gè)，那么，就輸出這個(gè)強(qiáng)連通分量?jī)?nèi)解的個(gè)數(shù)，否則輸出無(wú)解。
算法證明：
1：假設(shè)a和b都是最受歡迎的cow，那么，a歡迎b，而且b歡迎a，于是，a和b是屬于同一個(gè)連通分量?jī)?nèi)的點(diǎn)，所有，問(wèn)題的解集構(gòu)成一個(gè)強(qiáng)連通分量。
2：如果某個(gè)強(qiáng)連通分量?jī)?nèi)的點(diǎn)a到強(qiáng)連通分量外的點(diǎn)b有通路，因?yàn)閎和a不是同一個(gè)強(qiáng)連通分量?jī)?nèi)的點(diǎn)，所以b到a一定沒(méi)有通路，那么a不被b歡迎，于是a所在的連通分量一定不是解集的那個(gè)連通分量。
3：如果存在兩個(gè)獨(dú)立的強(qiáng)連通分量a和b，那么a內(nèi)的點(diǎn)和b內(nèi)的點(diǎn)一定不能互相到達(dá)，那么，無(wú)論是a還是b都不是解集的那個(gè)連通分量，問(wèn)題保證無(wú)解。
4：如果圖非連通，那么，至少存在兩個(gè)獨(dú)立的連通分量，問(wèn)題一定無(wú)解。
第一次用前向星存儲(chǔ)圖，在不方便開(kāi)臨街矩陣和臨街表的情況下，用前向星存儲(chǔ)邊，再開(kāi)一個(gè)數(shù)組存儲(chǔ)開(kāi)始和結(jié)束的位置，很方便。
#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逆序排列頂點(diǎn)，belong[]-----判斷各點(diǎn)屬于哪個(gè)分量
int order=0,indx=0;
bool noout[10001],v[10001];//noout----判斷某強(qiáng)連通子圖是否出度為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;
}
}//處理數(shù)組下標(biāo)
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;
}