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